Forem: Arc

Guard Your Rust Code with Tests

Arc — Sun, 21 Sep 2025 14:28:48 +0000

In the world of software development, if there's one area that has the highest ratio of importance to neglect, it has to be testing. Often, after we finish writing the code for a feature, we do a simple check to see if it works, maybe test a few edge cases, and then declare development complete. As the codebase grows, every code modification becomes a gamble. Adding new logic is one thing, but modifying or refactoring existing logic can cause things to break in distant, unforeseen places. This is where the value of testing becomes apparent. For instance, I'm currently working on a large personal project. It's about 20% complete, but the codebase has already exceeded 15,000 lines and includes 259 test cases. Now, after iterating on a crate, I have to run the full test suite. Otherwise, not even a deity could guarantee my changes haven't broken anything.

Unlike writing application code, most people (myself included) find writing test cases to be a tedious task. It's hard for anyone to stay motivated to do something boring and not immediately essential. Fortunately, we are in the age of AI, and writing test cases is right in the comfort zone of AI coding agents. AI can think of various edge cases we might miss, write large amounts of repetitive and mechanical test cases, and doesn't require much thought.

This article will introduce several common types of testing and their related crates in Rust. However, it won't go into too much detail about their usage, because I let AI write them for me, and I'm too lazy to study the specific usage of each crate myself.

Property Testing

Property testing (prop test) refers to testing whether something satisfies its corresponding properties. The test target is a structure. For example, in my red-black tree code, I need to test if the red-black tree still satisfies its five properties after multiple rounds of operations:

use proptest::prelude::*;
use rb_tree::RBTree;

proptest! {
    #[test]
    // proptest generates a large number of random inputs for the test function,
    // allowing specification of type, range, etc.
    fn rb_tree(keys in prop::collection::vec(any::<i32>(), 1..=1000)) {
        let mut tree = RBTree::new();
        for key in &keys {
            tree.insert(*key, *key);
            // The validate method checks if the tree is valid
            if let Err(e) = tree.validate() {
                panic!("Tree invalid after initial insertions: {}", e);
            }
        }

        let mut unique_keys: Vec<_> = keys.clone();
        unique_keys.sort();
        unique_keys.dedup();

        for key in &unique_keys {
            assert!(tree.get(key).is_some());
        }


        for (index, key) in unique_keys.iter().enumerate() {
            tree.remove(key);
            if index % 100 == 0 {
                // The validate method checks if the tree is valid
                if let Err(e) = tree.validate() {
                    panic!("Tree invalid after removing {}: {}", key, e);
                }
            }
        }
    }
}

Property testing can be done using the proptest crate. It generates a large number of random inputs for the test function, covering as many cases as possible, because we don't care about the specific test values, only whether the structure satisfies the required properties after each operation.

Differential Testing

Differential testing refers to testing whether something is consistent with another standard implementation. The test target can be a structure or a function/method. Again, using the red-black tree as an example, the purpose of a red-black tree is to implement an ordered set. How can I ensure my logic is correct? The simplest way is to compare it with a standard library ordered set like BTreeMap. By performing the exact same operations on both, if their outputs are identical after every step, it indicates the logic is correct.

Similarly, we use proptest to generate a large number of random inputs and combine them into random operations:

use proptest::prelude::*;
use rb_tree::RBTree;
use std::collections::BTreeMap;

#[derive(Debug, Clone)]
enum Op<K, V> {
    Insert(K, V),
    Remove(K),
}

proptest! {
    #[test]
    fn fast_differential_test(
        ops in prop::collection::vec(prop_oneof![
            (any::<u16>(), any::<u16>()).prop_map(|(k, v)| Op::Insert(k, v)),
            any::<u16>().prop_map(Op::Remove),
        ], 1..2000)
    ) {
        let mut my_tree = RBTree::new();
        let mut std_tree = BTreeMap::new();

        for (i, op) in ops.iter().enumerate() {
            match op {
                Op::Insert(k, v) => {
                    my_tree.insert(k, v);
                    std_tree.insert(k, v);
                },
                Op::Remove(k) => {
                    my_tree.remove(&k);
                    std_tree.remove(&k);
                }
            }

            if i % 100 == 0 {
                if let Err(e) = my_tree.validate() {
                    panic!("Tree invalid after remove iteration {}: {}", i, e);
                }
            }

            assert_eq!(my_tree.len(), std_tree.len());
        }

        // For efficiency, we only compare once after all operations are done.
        // If the comparison operation is not expensive, it can be done after each operation.
        let my_vec: Vec<_> = my_tree.iter().map(|(k, v)| (*k, *v)).collect();
        let std_vec: Vec<_> = std_tree.iter().map(|(k, v)| (*k, *v)).collect();
        assert_eq!(my_vec, std_vec, "Final content mismatch with BTreeMap");

        my_tree.validate().expect("Final tree structure is invalid");
    }
}

Snapshot Testing

Actually, this whole article was just an excuse to talk about this part, because snapshot testing might be a relatively niche topic. A long time ago when I was writing React, the testing tools would mysteriously generate a bunch of snapshot files. I didn't know what they were for at the time, so I deleted them all and configured the tool not to generate them. Recently, while writing a JS parser, the boomerang from years ago finally came back and hit me.

In snapshot testing, we pass a value during the first test run, serialize a snapshot of it into a format (like JSON, YAML), and save it as a local file. In all subsequent tests, this value is compared against the existing file. If the comparison fails, the test fails.

In Rust, we use insta for snapshot testing. For example, if we want to test a sorting function sort, we can write:

#[test]
fn test() {
  let input = [3, 5, 2, 4, 1];

  insta::assert_json_snapshot!(sort(input));
}

On the first run, insta will write the value of sort(input), let's assume it's [1, 2, 3, 4, 5], into a file with a .snap.new extension in the snapshots directory. The file header contains metadata like the call location, and the file body is the JSON content [1, 2, 3, 4, 5].
On the first run, the generated file will have a .new suffix, and the assert will fail. So if you call assert_json_snapshot multiple times in a function and run it with cargo test, the whole test will fail at the first assertion, and the subsequent ones won't execute. Therefore, it's best to install cargo-insta and run tests with cargo insta test. This will generate all .snap.new files at once.

After generation, you need to run cargo insta review to review all snapshot files. Accept the ones that are correct and reject the ones that are not, then go fix your logic. The accepted .snap.new files will have the .new suffix removed, becoming .snap files, which will be used for comparison in subsequent tests.

You might ask, this doesn't seem very useful. I could just write:

#[test]
fn test() {
  let input = [3, 5, 2, 4, 1];

  assert_eq!(sort(input), [1, 2, 3, 4, 5]);
}

I actually discovered snapshot testing because I was recently writing a JS parser for practice, and I naturally thought of testing like this:

assert_eq!(
  parse("call(a, b)").to_json(),
  r#"{
  "type": "CallExpression",
  "start": 0,
  "end": 9,
  "callee": {
    "type": "Identifier",
    "start": 0,
    "end": 3,
    "name": "add"
  },
  "arguments": [
    {
      "type": "Identifier",
      "start": 4,
      "end": 5,
      "name": "a"
    },
    {
      "type": "Identifier",
      "start": 7,
      "end": 8,
      "name": "b"
    }
  ],
  "optional": false,
}"#
);

Even a simple CallExpression produces this much text. For a slightly more complex AST, it's impossible to write by hand, let alone asking an AI to write it.

Snapshot testing is specifically designed to solve this problem. For test cases that are impossible to write by hand, it allows them to be generated automatically. You just need to ensure that the first generation is correct.

Your next question should be: I need to write tests precisely because I don't know if my code is correct, but now you're asking me to ensure the first generation is correct. This is a classic deadlock and the biggest problem with snapshot testing. Although insta provides a review capability, I believe you (and I) don't have the patience to look at them, because these snapshots are usually very large.

There's no perfect solution to this problem. Generally, it's combined with other testing methods, such as adding some assertions beforehand to ensure key points are correct. Of course, my specific scenario is very easy to test. When generating the initial snapshot, for each piece of input JS code, I start a Node.js process, pass the JS code and the Rust-generated AST to it. Node then uses Babel to generate a Babel AST, and I compare the two for consistency. So, my code has an external "cheat" for the initial test. In theory, I could completely abandon snapshot testing and just compare with Babel in the formal tests, but creating a Node.js process is quite expensive. In comparison, using snapshots has a much smaller performance overhead.

Summary

This article introduced three testing methods:

Property Testing: Tests whether a structure maintains certain properties at all times.
Differential Testing: Tests whether the output of a structure or function is consistent with a standard implementation.
Snapshot Testing: Compares against a snapshot generated on the first run, often used when the expected value is difficult to write by hand.

With the protection of various tests, we can iterate on existing features with confidence, leading to an order-of-magnitude improvement in development efficiency. Especially in this age of AI, AI can help us write any test case, providing a natural guard. And, the satisfaction of seeing cargo nextest r pass is much stronger than cargo build!

Rust Data Structures - Skip List

Arc — Thu, 04 Sep 2025 15:39:16 +0000

Rust Data Structures - Skip List

A skip list is an ordered data structure based on a linked list that allows for fast lookups and insertions. The time complexity for insertion, lookup, and deletion is O(log N), and it remains sorted after these operations. Redis's SortedSet data type is implemented using a skip list.

Structure of a Skip List

The skip list is an elegant data structure that perfectly embodies the "space-for-time" trade-off. Let's consider the problem with a traditional sorted linked list:

HEAD -> (-10) -> (1) -> (2) -> (3) -> (10) -> TAIL

If we want to insert a node with a key of 5, we need to place it between 3 and 10. However, the complexity of this insertion is O(N) because we have to traverse the list to find the correct position. The same applies to search and delete operations.

The reason for this is that traversal can only happen one node at a time, as each node has only a single next pointer. A skip list, as the name suggests, allows for "skipping" during traversal. A node in a skip list has multiple levels of pointers, stored in a forward array. Pointers at higher levels jump farther, while the pointer at the lowest level always points to the immediate next node.

This might be hard to grasp from the definition alone, but the structure of a skip list becomes clear with a diagram:

L3 |HEAD -> (-10: -10)---------- -> (2: 2)---------------------- -> TAIL
   |(1)     (2)                     (3)
   ||       |                       |                               |
L2 |HEAD -> (-10: -10) -> (1: 1) -> (2: 2)---------------------- -> TAIL
   |(1)     (1)           (1)       (3)
   ||       |             |         |                               |
L1 |HEAD -> (-10: -10) -> (1: 1) -> (2: 2)---------- -> (10: 10) -> TAIL
   |(1)     (1)           (1)       (2)                 (1)
   ||       |             |         |                   |           |
L0 |HEAD -> (-10: -10) -> (1: 1) -> (2: 2) -> (3: 3) -> (10: 10) -> TAIL
   |(1)     (1)           (1)       (1)       (1)       (1)

Here, (-10: -10) represents the key and value. The (2) below it indicates that the pointer at this level jumps to the 2nd node after it, meaning it skips 1 node in between.

Although a skip list is drawn like a matrix, it is still fundamentally a linear linked list. In reality, the entire skip list consists of n actual nodes plus two optional sentinel nodes (head, tail). The difference is that each node has multiple pointers instead of just one. Higher-level pointers jump farther, and lower-level pointers make shorter jumps.

All traversals in a skip list start from the top-left corner, which is the head node at the highest level (self.level). The process involves moving right and then moving down. Let's take searching for 10 as an example:

Start at the head node, at level 3.
Jump right to the -10 node.
Jump right to the 2 node.
The next node at this level is the tail, so move down to level 2.
The next node at level 2 is also the tail, so move down to level 1.
The next node is 10. The search is complete.

Moving down a level has almost no performance cost (it's just a calculation like current_level -= 1), so we can ignore it for now. The search operation above visited 3 nodes (excluding the head) to find the node 10. If we were to traverse from level 0 (the basic linked list), it would require 5 visits. Therefore, the search performance of a skip list is better than that of a linked list.

Randomness

Unlike strictly balanced ordered structures like AVL or Red-Black trees, the balance of a skip list is probabilistic because the level of each node is generated randomly. Ideally, there should be fewer nodes at higher levels, allowing for longer jumps and skipping more nodes.

The simplest way to generate the level for a new node is generally:

fn random_level() -> i32 {
  let mut level = 0;

  while rand::random::<f64>() < 0.5 && level < MAX_LEVEL {
    level += 1;
  }

  level
}

This means a node's level has a 50% chance of increasing by 1 on each coin flip, up to a maximum height. So, the probability of level = 1 is 50%, level = 2 is 25%, level = 3 is 12.5%, level = 4 is 6.25%, and so on.

The value of MAX_LEVEL is an attribute of the skip list itself, typically 16 or 32. It represents the maximum possible height, not the maximum number of elements. Even if the maximum height is reached, you can still insert elements indefinitely, but the performance optimization becomes less significant.

Due to this randomness, the structure of a skip list is not deterministic. For the exact same sequence of insertions, the resulting skip list structures will very likely be different. Despite the randomness, with our rand_level method, the expected number of nodes at any level is half that of the level below it. This means that moving down a level eliminates about half of the remaining nodes, similar to a binary search tree. Therefore, the average time complexity is O(log N).

Optimization for Random Access

The skip list described so far has a problem: it cannot quickly access the nth element. You still have to traverse from level 0, the linked list structure. However, this is easy to solve. We can add a span value to each pointer in the forward array, indicating the number of nodes the pointer skips over (including the target node). This way, we can accumulate the total number of nodes skipped during traversal. When the total equals n, we've found our element. If a jump would overshoot the target, we move down a level. Since the span of every pointer at level 0 is always 1, we are guaranteed to find the nth element as long as n is less than the total number of nodes.

Data Structure

pub trait Key: Ord {} // Key must implement Ord
impl<T> Key for T where T: Ord {}

pub trait Value {}
impl<T> Value for T {}

pub struct Node<K, V> {
    key: MaybeUninit<K>,
    value: MaybeUninit<V>,
    forward: Vec<ForwardPtr<K, V>>,
    level: usize,
}

impl<K: Key, V: Value> Node<K, V> {
    pub fn key(&self) -> &K {
        unsafe { self.key.assume_init_ref() }
    }

    pub fn key_mut(&mut self) -> &mut K {
        unsafe { self.key.assume_init_mut() }
    }

    pub fn value(&self) -> &V {
        unsafe { self.value.assume_init_ref() }
    }

    pub fn value_mut(&mut self) -> &mut V {
        unsafe { self.value.assume_init_mut() }
    }
}

type NodePtr<K, V> = NonNull<Node<K, V>>;

#[derive(Debug)]
struct ForwardPtr<K, V> {
    ptr: NodePtr<K, V>,
    span: usize, // forward_ptr carries span information
}

// We must manually implement Clone here, we can't use derive
// because #[derive(Clone)] would generate code like:
// 
// impl<K: Clone, V: Clone> Clone for ForwardPtr<K, V>
// 
// which requires K and V to implement Clone, but we cannot restrict K and V to be Clone.
impl<K, V> Clone for ForwardPtr<K, V> {
    fn clone(&self) -> Self {
        Self {
            ptr: self.ptr,
            span: self.span,
        }
    }
}

impl<K, V> Copy for ForwardPtr<K, V> {}

impl<K, V> PartialEq for ForwardPtr<K, V> {
    fn eq(&self, other: &Self) -> bool {
        self.ptr == other.ptr
    }
}

impl<K, V> Default for ForwardPtr<K, V> {
    fn default() -> Self {
        Self {
            ptr: NonNull::dangling(),
            span: 0,
        }
    }
}

#[derive(Debug)]
pub struct SkipList<K: Key, V: Value> {
    head: NodePtr<K, V>,
    tail: NodePtr<K, V>,
    level: usize, // The level of the skip list is equal to the level of the highest node
    len: usize,
}

const MAX_LEVEL: usize = 32;

Similar to the Red-Black Tree, since the key and value of the sentinel nodes head and tail cannot hold values, we need to use MaybeUninit. Unlike the Red-Black Tree, the IntoIter for a skip list can release nodes after each iteration because it doesn't need to preserve the tree structure to find the successor. Therefore, we don't need to use ManuallyDrop for the key and value.

Insertion

The insertion/deletion logic for a skip list is much simpler than for a Red-Black Tree. The core idea is to traverse from the highest level down, maintaining an update array. After traversing level i, the current node pointer is stored in update[i]. Once the initial traversal is complete, we iterate through the update array from the highest level down. For an insertion, we insert the new node at level i after the node pointed to by update[i].

pub fn insert(&mut self, key: K, value: V) -> Option<V> {
    let level = Self::rand_level(); // Generate a random level

    // If the new level is greater than the skip list's current level, update the list's level
    // and make the new level pointers in the head point to the tail.
    if level > self.level {
        for _ in (self.level + 1)..=level {
            unsafe {
                self.head.as_mut().forward.push(ForwardPtr {
                    ptr: self.tail,
                    span: self.len + 1,
                });
            }
        }
        self.level = level;
    }

    // update[i] stores the pointer to the node at level i that needs to be updated.
    // It points to the last node at level i with a key less than the new key.
    let mut update = vec![NodePtr::dangling(); self.level + 1];
    let mut steps = vec![0; self.level + 1];
    let mut step = 0;

    let mut cur = self.head;
    for i in (0..=self.level).rev() {
        loop {
            let cur_node_ref = unsafe { cur.as_ref() };
            let next = cur_node_ref.forward[i].ptr;

            if self.is_tail(next) {
                break;
            }
            let next_key = (unsafe { next.as_ref() }).key();

            // If the node's key is less than the current key, continue.
            if next_key < &key {
                step += cur_node_ref.forward[i].span;
                cur = next;
            } else {
                break;
            }
        }
        update[i] = cur;
        steps[i] = step;
    }

    let mut next = unsafe { cur.as_ref() }.forward[0].ptr;

    if !self.is_tail(next) && unsafe { next.as_ref() }.key() == &key {
        // If the key already exists, update the value and return the old value.
        let old_v = std::mem::replace(unsafe { next.as_mut() }.value_mut(), value);

        return Some(old_v);
    }

    cur = next;

    step += 1;

    let mut forward = vec![ForwardPtr::default(); level + 1];

    let new_node = Box::new(Node {
        key: MaybeUninit::new(key),
        value: MaybeUninit::new(value),
        forward: vec![],
        level,
    });

    let mut new_node_ptr = NonNull::from(Box::leak(new_node));

    // Update each update[i]
    // new_node.forward[i] = update[i].forward[i]
    // update[i].forward[i] = new_node
    for i in (0..=self.level).rev() {
        let update_node = unsafe { update[i].as_mut() };
        if i <= level {
            let cur_span = step - steps[i];

            forward[i] = ForwardPtr {
                ptr: update_node.forward[i].ptr,
                span: steps[i] + update_node.forward[i].span - step + 1,
            };

            update_node.forward[i].ptr = new_node_ptr;
            update_node.forward[i].span = cur_span;
        } else {
            // Update the span of the pointers in update[i] above the new node, because a node was inserted.
            update_node.forward[i].span += 1;
        }
    }

    unsafe { new_node_ptr.as_mut() }.forward = forward;

    self.len += 1;
    None
}

Deletion

Deletion is similar to insertion. A minor difference is that it returns None if the node to be deleted is not found. The overall logic is also to start from the top-left, find the update[i] for each level, and then perform the linked list deletion level by level. Note that update[i] is not the node to be deleted, but its predecessor at each level. Pseudocode:

update[i].forward[i] = update[i].forward[i].forward[i];
drop(node_to_remove); // node_to_remove is found during traversal

Search

Search is also similar, starting from the top-left corner. We won't go into detail here.

Memory Management

Since we are using raw pointers, we need to manually free the memory.

impl<K: Key, V: Value> Drop for SkipList<K, V> {
    fn drop(&mut self) {
        unsafe {
            let mut cur = self.head.as_ref().forward[0].ptr;

            while !self.is_tail(cur) {
                let next = cur.as_ref().forward[0].ptr;
                let _ = Box::from_raw(cur.as_ptr());
                cur = next;
            }

            let _ = Box::from_raw(self.head.as_ptr());
            let _ = Box::from_raw(self.tail.as_ptr());
        }
    }
}

Performance Comparison

Here is a performance comparison for lookups between a Skip List, a Linked List, and a BTreeMap:

As you can see, as the number of elements increases, the performance of the linked list deteriorates sharply, while the performance of the skip list and BTreeMap remains almost constant. This again proves that the overall time complexity for lookups in a skip list is O(log N).

Conclusion

Both being ordered structures with O(log N) time complexity, the skip list is much simpler to implement than a Red-Black Tree. Even if you are familiar with both, the insertion, deletion, and rotation operations for a Red-Black Tree can take a full day to write, whereas a complete skip list can be written in half a day. Furthermore, the skip list's elegant embodiment of the space-for-time trade-off makes it a very graceful data structure.

Complete Code

https://github.com/Arichy/skip-list-rs

Rust Data Structures - Red-Black Tree

Arc — Tue, 02 Sep 2025 18:01:38 +0000

The Red-Black Tree is a renowned data structure, prized for its self-balancing properties, which ensure that insertion and deletion operations both have a complexity of O(logN). This article will explain how to implement a Red-Black Tree in Rust, divided into three parts:

Introduction to Red-Black Trees
Red-Black Tree Operations
Considerations related to Rust's language features

1. Introduction to Red-Black Trees

A Red-Black Tree is essentially a Binary Search Tree (BST). If you're not familiar with BSTs, here's a brief introduction:

1.1 Binary Search Tree (BST)

A Binary Search Tree is a special type of binary tree with a specific property: for any given node, all keys in its left subtree are less than its own key, and all keys in its right subtree are greater than its own key. This allows for binary searches. To find a target_key, if the current_key == target_key, you've found it. If current_key < target_key, the target must be in the right subtree, so you continue searching there. If current_key > target_key, the target must be in the left subtree. Each step eliminates half of the remaining nodes, resulting in a search time complexity of O(logN).

However, the ideal is often far from reality. The structure of a BST depends on the insertion order. In an extreme case, such as inserting numbers sequentially from 1 to 1,000,000, nodes will be continuously added to the right. The BST degenerates into a linked list, and the time complexity for searches degrades to O(N).

Therefore, keeping the binary tree balanced—ensuring the height difference between the left and right subtrees of any node is not too large—is crucial. The most common approach is to add an extra set of rules to the basic BST rules to maintain balance after any operation. Common examples include AVL trees and Red-Black Trees.

1.2 Rules of Red-Black Trees

A Red-Black Tree has five rules, all aimed at one goal: keeping the tree balanced after any operation.

Every node is either red or black.
The root node is black.
All leaf nodes (NIL) are black. It's important to note the concept of NIL nodes. A NIL node is an empty node, distinct from the actual nodes you insert, find, or delete. For example, a single real node (the root) will have two NIL children. If a real node has only one real child, its other child is a NIL node.
Two red nodes cannot be adjacent. In other words, the children of a red node must be black.
For any given node, all simple paths from the node to its descendant NIL nodes contain the same number of black nodes (this property is called the Black-Height).

The key lies in rules 4 and 5. The combination of "no two red nodes can be adjacent" and "every path must have the same black-height" leads to two extreme scenarios:

Alternating red and black nodes.
Only black nodes, no red nodes.

In the most extreme case, the height of a path in scenario 1 can be at most twice the height of a path in scenario 2. This guarantees the tree's balance: the height of any path cannot be more than twice the height of any other path. This balance ensures the O(logN) time complexity for insertion, search, and deletion.

2. Introduction to Red-Black Tree Operations

The operations on a Red-Black Tree are relatively complex. Rote memorization is ineffective; it's crucial to understand the core purpose of each operation and why it works. For each step below, I will explain why it resolves the conflict. For a complex data structure like a Red-Black Tree, I personally believe it's not necessary to force ourselves to derive every correct step from scratch, but it is necessary to understand why the standard correct operations resolve conflicts. This way, when you revisit it later, you can easily deduce the rotation directions and color changes, rather than reciting them like a textbook verse, which is bound to be forgotten over time.

Since Red-Black Tree operations involve multiple relative nodes, we'll use the following letters to denote relationships:

N: New node
P: Parent node of N
G: Grandparent node (P's parent)
S: Sibling node of P
U: Uncle node (P's sibling)
FN: Far Nephew node (the child of U that is farther from N)
NN: Near Nephew node (the child of U that is closer to N)

Red-Black Trees have two fundamental operations:

Recoloring
Rotation

For each operation, we need to focus on its impact, specifically on rules 4 and 5.

2.1 Recoloring

Recoloring means changing a node's color to a specific color. Recoloring affects 2 paths.

A few notes about the diagrams in this article:

Black nodes are drawn in gray because there is also a concept of Double-Black, which will be drawn in pure black.
A circle represents a real node. The box above it represents an ancestor, and the box below represents an entire subtree. A box indicates that we don't care about the specific nodes, which may not even exist; it just represents that position. The number inside the bottom box represents the number of black nodes on the path from up to itself.

The diagram above shows that after N changes from red to black, the black-path from up to both subtrees increases by 1. If the tree was balanced before, it is now unbalanced (assuming up is a real node, meaning N is not the root).

2.2 Rotation

Rotations are divided into left and right rotations:

A left rotation on a node promotes its right child to its position, making itself the left child of the former right child. The former right child's left child becomes the new right child of the original node.
A right rotation on a node promotes its left child to its position, making itself the right child of the former left child. The former left child's right child becomes the new left child of the original node.

Only a node with a real left child can be right-rotated, and only a node with a real right child can be left-rotated.

The red box after each operation indicates that the number of black nodes from up to that box has changed, causing an imbalance. It's crucial to note that we assume the initial state before each operation is balanced. For example, in the diagram above, before the rotation, the black-node counts from up to the three bottom boxes are 1, 1, and 0. Although not all equal, this is a balanced state because the box with 0 could have another black node below it, as long as the total count to the NIL nodes is the same. Therefore, our goal is to maintain balance, i.e., keep the numbers in the affected boxes unchanged, not to make them identical. After the rotation, the black-node counts from up to LL and LR remain 1, but the count to N's right child changes from 0 to 1, meaning this path's black-height has increased by one, breaking the balance.

The core of rotation is to reorganize nodes locally. This process might temporarily change the black-node count of some paths. Our goal is to restore the black-height of all affected paths to be consistent with the state before the operation, thus maintaining the balance of the entire tree.

Due to the symmetrical nature of Red-Black Tree structures and rotations, this article will only illustrate one type of structure + rotation. The other is a mirror image.

3. Search

Searching in a Red-Black Tree is no different from a standard BST. Since each node stores a key-value pair, the search process is independent of color and follows the BST search procedure.

4. Insertion

Insertion is where the difficulty begins. First, a key point: an inserted node is always a real leaf node, meaning it's attached directly under an existing real node, not inserted by breaking a connection in the middle of the tree. The initial steps of insertion in a Red-Black Tree are identical to a BST: find the insertion position, then create and insert the new node. After this step, the Red-Black Tree's specific operations begin.

First, let's consider a question: should the newly inserted node be colored red or black? If it's red, rule 5 is not violated because adding a red node doesn't affect the black-height. However, it might violate rule 4 if its parent is also red. If it's black, rule 4 is not violated, but rule 5 is definitely violated, as the black-height of this path will increase by 1. Fixing a black-height violation is harder than fixing a red-red conflict. Choosing the lesser of two evils, we initialize every new node as red.

4.1 Parent P is Black

In this case, no rules are violated, so we're done.

4.2 Parent P is Red

This creates a red-red conflict that needs to be resolved. We can't just change N to black, as that would be the same as initializing it as black in the first place. We need to find a way to make P black. P cannot be directly changed to black, as this would increase the black-height of its path by 1. If P turns black and G (P's parent, N's grandparent, which must be black since P is red) turns red, the black-height through P remains unchanged, which is perfect. However, this causes two potential problems:

The black-height of the path through G's other child, U (P's sibling, N's uncle), decreases by 1.
If uncle U is red, G turning red will create a new red-red conflict. If U is black, this problem doesn't occur, but problem 1 remains.

So, we must consider cases based on U's color.

4.2.1 Uncle U is Red

This is the easiest case to solve. Simply change U to black. This solves both problems at once. So we have our first rule: If U is red, change P and U to black, and change G to red. This is like G passing its "blackness" down to its children P and U, while it becomes red. The number of black nodes on the paths G-P and G-U remains 1, maintaining balance. However, a new problem arises: G turning red might conflict with its own parent. This is also easy to handle. Since we've been solving red-red conflicts from the start, we can simply recurse upwards, pushing the problem up the tree until we reach the root. If the root becomes red, we can just change it to black. Changing the root from red to black increases the black-height of the entire tree by 1, which keeps it balanced.

4.2.2 U is Black

In this case, we can't solve it with just recoloring; any change will break the balance. So, rotation is needed. We need to consider the alignment of N-P-G. If they form a straight line, it's a simpler case.

How should we rotate? We can use a process of elimination.

N cannot necessarily be rotated, as it might not have children (e.g., when just inserted).
Similarly, U might not have a right child and thus cannot be rotated.
P could be right-rotated, bringing N up and P down. If N then becomes black, the black-height of path a increases by 1, breaking the balance. To compensate, if we make G red, the left side of G is balanced, but the right side (the G-U path) has its black-height reduced by 1, still unbalanced. So this is not a viable solution.
This leaves only rotating G as a meaningful option. G cannot be left-rotated because U is not necessarily a real child. If N is a newly inserted node, U must be a NIL node. This is because N replaced a NIL. Before this, the tree was balanced, so the black-height from G to that NIL was 2 (including the NIL, or 1 without it; the result is the same). Since U is black, if U were a real node, the black-height from G to a NIL below U would be at least 3 (G, U, and the NIL itself). Therefore, U must be a NIL to maintain a black-height of 2.

So, the only remaining option is a right rotation on G. Let's see what that looks like:

As you can see, the black-node counts to b and c from up are unchanged, but the count to a has decreased by 1. This is because we moved the shared black node G to be exclusively on the right side, reducing the black-height on the left.

At this point, we could simply change N to black, which would restore the count for a to 1, maintaining balance. The only concern is that the node under up is now the red P, which could create another red-red conflict. But that's okay; just like in the case where the uncle was red, we can push the problem upwards and solve it recursively.

If you've studied Red-Black Trees before, you might be confused at this point. "Wait, all the articles I've read say to change P to black and G to red." Let's see the effect of that:

No conflicts at all! The black-heights at positions a, b, and c are all restored to their original balanced numbers. And since P is now black, it can't conflict with its parent. The tree is now valid, and the fix is complete.

Both of the above operations can solve the problem, but the standard solution given in all articles and textbooks is the second one: the promoted P becomes black, and the demoted G becomes red. This is more efficient, with a time complexity of O(1). The first approach, if P creates a new red-red conflict with its parent, requires recursive fixing up the tree, with a worst-case time complexity of O(logN).

This also shows that there are multiple ways to fix a Red-Black Tree; the standard textbook method is just the recognized, proven optimal solution. From now on, I will use the standard solution directly and explain its validity step-by-step.

The next case is when N-P-G form a zig-zag line (or a triangle). We first need to convert it into a straight line. This is simple: rotate P to bring the red N up and P down, creating a straight N-P-G line, then apply the solution for the straight-line case.

This concludes the insertion for Red-Black Trees. While memorizing every step for every case is pointless, a few key points can help with recall:

Check the uncle's color. If it's red, the uncle and parent both turn black, the grandparent turns red, and the problem is pushed upwards.
If the uncle is black, check the N-P-G line. A straight line is easiest: perform one rotation on G, then swap the colors of P and G (the one that goes up becomes black, the one that goes down becomes red).
If it's a zig-zag, first rotate P to convert it into a straight-line case.

5. Deletion

Deletion is more complex than insertion. With insertion, we initialize the new node as red, only potentially violating the easily-fixed rule 4, not the harder-to-fix rule 5. Deletion, however, might remove a black node, violating rule 5.

Like insertion, deletion starts with a standard BST deletion. If you're not familiar with BST deletion, here's a quick review:

If the node to be deleted has no children, just delete it.
If it has one real child, replace the node with its child.
If it has two real children, find its in-order predecessor (the rightmost node in the left subtree) or successor (the leftmost node in the right subtree), swap their positions, and then delete the node. After the swap, the node to be deleted will have at most one child.

So, the node actually deleted in a deletion operation has at most one real child. Red-Black Tree deletion builds on this foundation.

5.1 Deleted Node is Red

In this case, do nothing. No rules are violated. The process ends.

5.2 Deleted Node is Black

Now the trouble begins. We will definitely violate rule 5, and possibly rule 4 if the parent is red and the replacement child is also red. This is where the concept of "Double-Black" comes in. We mark the replacement child as Double-Black. There will always be a replacement child, even if it's a NIL node. If you're familiar with the Double-Black concept, you might wonder why it's called "Double-Black" when the path is actually missing a black node. It's because we are conceptually adding an extra "blackness" to the replacement child, pretending the path's black-height hasn't changed and the tree is still balanced. Our main job then becomes to eliminate this Double-Black mark.

There are two ways to eliminate a Double-Black:

Find a way to add an extra black node to this side, allowing the Double-Black node to remove its mark.
Move the Double-Black mark to a red node, which then turns black, naturally clearing the mark.

Seeing method 2, you can probably guess that if the replacement node is red, everything is fine. We just change it to black. A red-to-black change never causes a red-red conflict and only increases the black-height by 1, which is exactly what we need to compensate for the deleted black node. So, the following discussion assumes the replacement node is black, which we mark as Double-Black (let's call it X).

5.2.1: X's Sibling S is Red

We can't just pass X's problem to S. Imagine a balanced scale; moving a weight from the right side to the left will surely unbalance it. This situation is tricky. We need to transform it into a case where S is black. We do this by rotating P (which must be black), bringing the red S up. The promoted S turns black, and the demoted P turns red. P's other child becomes one of S's children; this child must be black and becomes X's new sibling. We now have the "X's sibling is black" case.

5.2.2: X's Sibling S is Black

If we could, like in insertion, make the parent and uncle black and the grandparent red, that would be great. Similarly, we want X to lose one "blackness" to become a normal black node, S to lose one "blackness" to become red, and then P to become black, as if the two children passed their "blackness" up to P. This requires a precondition: S can become red, meaning both of its children are black.

5.2.2.1: S is black, and both its children (FN, NN) are also black

In this case, S can lose a "blackness" and become red, X can lose a "blackness" and become a normal black node, and P gains a "blackness". If P was red, it just turns black. If P was black, the new X is P. Just as the red-red conflict was pushed up the tree during insertion, we push the Double-Black problem up, recursively eliminating it starting from P.

5.2.2.2: S is black, FN (Far Nephew) is red

This is the most complex case that doesn't transform into another case.

Here, P's color is unknown and unimportant. We'll represent the number of black nodes it contributes as P?, which can be 0 or 1. Similarly, NN's color is unknown, and its contribution is NN?, also 0 or 1. The tree is currently balanced (note that X contributes 2 black nodes).

First, right-rotate P:

The balance is now broken. The left side, FN down, has lost P?, and the right side, X down, has gained 1. This is understandable because we moved P to the right and S up.

Next, swap the colors of S and P:

S now contributes P? black nodes because it inherited P's color. So, FN down becomes P?, and X down is still P? + 1 + 2. These two positions are still not balanced.

Finally, we change FN to black, and X loses one "blackness" to become a normal black node:

Now, FN down is restored to P? + 1, and X down is restored to P? + 2. Both are balanced again. Perfect.

5.2.2.3: S is black, FN (Far Nephew) is black, NN (Near Nephew) is red

This needs to be converted to the "FN is red" case above, which can be done with one rotation and a recolor.

Initial state:

Left-rotate S:

Swap the colors of S and NN:

This transforms it into the "S is black, FN is red" case.

To summarize the key points for deletion:

If the deleted node is red, nothing happens.
Mark the replacement node as Double-Black. If a Double-Black meets a red node, it just turns black, and we're done.
If the replacement is black, look at its sibling. If the sibling can turn red, both it and the node lose one "blackness", passing it to the parent, which now has to solve the Double-Black problem.
If the sibling cannot turn red, look at the far nephew. If it's red, rotate P to bring S up, swap the colors of P and S, and the Double-Black is naturally eliminated.
If the far nephew is black but the near nephew is red, use a rotation to convert it to the "far nephew is red" case.

6. Rust Language-Specific Issues

Because Rust is a unique language, implementing a Red-Black Tree in it requires more considerations than in other languages, such as memory management, trait design, etc. If you're not interested in Rust, you can skip this section; the core Red-Black Tree content has already been covered.

6.1 Data Structure Design

First, let's consider the node structure. key, value, color, left, and right are essential. Since we need to frequently access the parent, grandparent, uncle, etc., we'll add a parent field for convenience.

Next, what kind of pointer should we use? In Safe Rust, one would typically use Rc + RefCell. However, for a low-level data structure like a Red-Black Tree with frequent pointer manipulations, Rc + RefCell can be cumbersome. So, we must venture into the world of Unsafe Rust, which is designed for such low-level scenarios. What about raw pointers? It's possible, but there's a better option: NonNull.

NonNull has the same size as a raw pointer *mut T, but the Rust compiler assumes NonNull is never null, a guarantee we must uphold. In this scenario, it's best to avoid null pointers to eliminate many null checks. So, we introduce a head sentinel node. Also, since NIL nodes are meaningful in a Red-Black Tree (they have a color), we'll add a nil sentinel node. While we could theoretically create a nil for every real node's empty child, this would waste memory. A single global nil sentinel is sufficient, with all null pointers pointing to it. The only issue is that when traversing, we can't get the real parent from nil's parent field, as the global nil's parent will be itself. This is a minor problem; when we might traverse to nil, we can just maintain a parent variable instead of relying on the parent pointer.

So, here is our first version of the RBNode struct:

#[derive(Debug, Clone, Copy, PartialEq)]
pub(crate) enum Color { // Double-Black is not a color, just represented by a pointer
    Red,
    Black,
}

pub(crate) type NodePtr<K, V> = NonNull<RBNode<K, V>>;

pub struct RBNode<K, V> {
    pub(crate) key: K,
    pub(crate) value: V,
    pub(crate) color: Color,
    pub(crate) left: NodePtr<K, V>,
    pub(crate) right: NodePtr<K, V>,
    pub(crate) parent: NodePtr<K, V>,
}

Since a Red-Black Tree needs to compare keys, and the comparison must be strict, all keys must implement the Ord trait. For extensibility, we'll add two new traits, Key and Value, and add constraints to the K and V generics:

pub trait Key: Ord {}
impl<T> Key for T where T: Ord {} // blanket implement, automatically implements Key for all types that implement Ord

pub trait Value {}
impl<T> Value for T {} // Although Value currently has no constraints, we add a Value trait for future extensions

pub struct RBNode<K: Key, V: Value> {...}

Next, let's consider the structure of RBTree itself. Based on the discussion above, we need a head sentinel pointing to the real root (any child will do; we'll choose the right child), and a nil node that all empty pointers point to. To easily get the current number of nodes without traversing, we'll maintain a len field.

pub struct RBTree<K: Key, V: Value> {
    header: NodePtr<K, V>,
    nil: NodePtr<K, V>,
    len: usize,
}

Now, a new problem: what should the key and value of the header and nil nodes be? This seems unanswerable because we can't just create an arbitrary key and value, especially the value. What if the value is a socket? We can't just open a TCP connection to be the head's value. You might say, "Just use the default value Value::default()." But that requires Value: Default, adding an unnecessary constraint, and it doesn't solve the example above. What if value is a TcpStream or something more complex?

This is where we need to use MaybeUninit. This type allows us to use a value without initializing it, similar to JavaScript.

So, we modify RBNode:

pub struct RBNode<K, V> {
    pub(crate) key: MaybeUninit<K>,
    pub(crate) value: MaybeUninit<V>,
    pub(crate) color: Color,
    pub(crate) left: NodePtr<K, V>,
    pub(crate) right: NodePtr<K, V>,
    pub(crate) parent: NodePtr<K, V>,
}

Now, when creating header and nil, we can do this:

impl<K: Key, V: Value> RBTree<K, V> {
    pub fn new() -> Self {
        let mut nil_node = Box::new(RBNode {
            key: MaybeUninit::uninit(), // Represents an uninitialized value; using it before initialization is UB
            value: MaybeUninit::uninit(),
            color: Color::Black,
            left: NonNull::dangling(), // Temporarily dangling, fixed immediately
            right: NonNull::dangling(),
            parent: NonNull::dangling(),
        });

        let nil_ptr = NonNull::from(&mut *nil_node);
        nil_node.parent = nil_ptr;
        nil_node.left = nil_ptr;
        nil_node.right = nil_ptr;

        let leaked_nil_ptr = NonNull::from(Box::leak(nil_node)); // Leak the value inside the Box to prevent it from being deallocated when the Box goes out of scope

        let header_node = Box::new(RBNode {
            key: MaybeUninit::uninit(),
            value: MaybeUninit::uninit(),
            color: Color::Black,
            left: leaked_nil_ptr,
            right: leaked_nil_ptr,
            parent: leaked_nil_ptr,
        });
        let leaked_header_ptr = NonNull::from(Box::leak(header_node));

        Self {
            header: leaked_header_ptr,
            nil: leaked_nil_ptr,
            len: 0,
        }
    }
}

Reading and writing MaybeUninit also requires unsafe, as it's a contract with the compiler: "I guarantee this value has been initialized." The compiler can't check this, so unsafe is used as a reminder. There are four common methods:

key.write(new_key) - Write a value
key.assume_init() - Take ownership
key.assume_init_ref() - Get an immutable reference
key.assume_init_mut() - Get a mutable reference

The last three methods require an unsafe block, and calling them on an uninitialized value results in UB (undefined behavior).

The rest of the Red-Black Tree implementation is straightforward. You'll find that the header and nil sentinels eliminate a lot of checks (though not all), such as whether the tree is empty, whether a sibling is null, etc.

6.2 Memory Management

Now comes a very difficult part of unsafe Rust: memory management (unfortunately, I have no C/C++ experience, so this was really hard for me). All the nodes of a Red-Black Tree are now leaked into memory. When the tree itself is dropped, we need to manually free every node:

impl<K: Key, V: Value> Drop for RBTree<K, V> {
    fn drop(&mut self) {
        // Collect all nodes
        let mut nodes = vec![];
        self.traverse(|node| {
            nodes.push(node);
        });

        // Drop each node
        for node in nodes {
            unsafe {
                let mut b = Box::from_raw(node.as_ptr());
                drop(b);
            };
        }

        // Don't forget the two sentinels
        unsafe {
            drop(Box::from_raw(self.header.as_ptr()));
            drop(Box::from_raw(self.nil.as_ptr()));
        }
    }
}

Similarly, when a node is removed, it also needs to be freed:

pub fn remove(&mut self, key: &K) -> Option<V> {
    let removed = self.bs_remove(key); // Delete according to binary search tree logic
    if self.is_nil(removed) { // If it's a nil node, do nothing, the key doesn't exist
        return None;
    }

    // Fix the red-black tree
    // ...

    unsafe {
        let removed_box = Box::from_raw(removed.as_ptr());
        let value = removed_box.value; // Transfer ownership of the value to the return value
        self.len -= 1;
        Some(value)
    }
}

So far, everything looks perfect. If we stop here, it's indeed fine; every node is correctly freed.

But if we want to add Iterator-related methods like in BTreeMap, we'll encounter new problems.
Let's implement IntoIterator for RBTree:

pub struct RBTreeIntoIter<K: Key, V: Value> {
    ptr: NodePtr<K, V>,
    rb_tree: RBTree<K, V>,
}

impl<K: Key, V: Value> Iterator for RBTreeIntoIter<K, V> {
  type Item = (K, V);

  fn next(&mut self) -> Option<Self::Item> {
    // ...
  }
}

impl<K: Key, V: Value> IntoIterator for RBTree<K, V> {
    type Item = (K, V);
    type IntoIter = RBTreeIntoIter<K, V>;

    fn into_iter(self) -> Self::IntoIter {
        let first = self.inorder_successor(self.header);

        RBTreeIntoIter {
            ptr: first,
            rb_tree: self,
        }
    }
}

Since RBTreeIntoIter takes ownership of RBTree, RBTreeIntoIter also needs to implement Drop to clean up the nodes:

impl<K: Key, V: Value> Drop for RBTreeIntoIter<K, V> {
    fn drop(&mut self) {
        let mut all_nodes = vec![];
        self.rb_tree.traverse(|node| {
            all_nodes.push(node);
        });

        // ???

        unsafe {
            drop(Box::from_raw(self.rb_tree.header.as_ptr()));
            drop(Box::from_raw(self.rb_tree.nil.as_ptr()));
        }
    }
}

When you try to write the drop method, you'll hit a fatal problem: each call to next transfers ownership of a node's key + value. When the node is later destroyed, it will try to destroy the key + value again, causing a double free. So, we need a mechanism to make the node skip dropping the key + value when it's destroyed. This mechanism is ManuallyDrop.

ManuallyDrop<T> tells the compiler to skip dropping the value itself, allowing the developer to drop it manually at the appropriate time. So, we update the RBNode structure:

pub struct RBNode<K: Key, V: Value> {
    pub(crate) key: MaybeUninit<ManuallyDrop<K>>,
    pub(crate) value: MaybeUninit<ManuallyDrop<V>>,
    pub(crate) color: Color,
    pub(crate) left: NodePtr<K, V>,
    pub(crate) right: NodePtr<K, V>,
    pub(crate) parent: NodePtr<K, V>,
}

This way, when RBNode is dropped, it will skip the key + value, not executing their drop methods. In the next method, we can safely take ownership of the key + value:

impl<K: Key, V: Value> Iterator for RBTreeIntoIter<K, V> {
    type Item = (K, V);
    fn next(&mut self) -> Option<Self::Item> {
        if self.rb_tree.is_nil(self.ptr) {
            return None;
        }

        // Find the next node
        let next = self.rb_tree.inorder_successor(self.ptr);

        unsafe {
            // Bitwise copy via ptr::read, key_wrapper and value_wrapper both have ownership
            let key_wrapper = std::ptr::read(self.ptr.as_ref().key.assume_init_ref());
            let value_wrapper = std::ptr::read(self.ptr.as_ref().value.assume_init_ref());

            // Unwrap to the inner types K, V
            let key = ManuallyDrop::into_inner(key_wrapper);
            let value = ManuallyDrop::into_inner(value_wrapper);

            self.ptr = next;
            Some((key, value))
        }
    }
}

impl<K: Key, V: Value> Drop for RBTreeIntoIter<K, V> {
    fn drop(&mut self) {
        // Use an empty loop to consume all remaining (K, V) pairs
        for _ in &mut *self {}

        let mut nodes_to_dealloc = vec![];

        self.rb_tree.traverse(|node_ptr| {
            nodes_to_dealloc.push(node_ptr);
        });

        for node_ptr in nodes_to_dealloc {
            unsafe {
                // Thanks to the ManuallyDrop wrapper, the key + value of all nodes will not be dropped again
                drop(Box::from_raw(node_ptr.as_ptr()));
            }
        }

        unsafe {
            drop(Box::from_raw(self.rb_tree.header.as_ptr()));
            drop(Box::from_raw(self.rb_tree.nil.as_ptr()));
        }
    }
}

There's one small issue left. Because RBTreeIntoIter takes ownership of RBTree, when the former is dropped, the latter's drop will also be called, causing all nodes to be double-freed. This is easy to solve: we can apply the same pattern and change RBTreeIntoIter's rb_tree field to ManuallyDrop<RBTree<K,V>>:

pub struct RBTreeIntoIter<K: Key, V: Value> {
    ptr: NodePtr<K, V>,
    rb_tree: ManuallyDrop<RBTree<K, V>>,
}

7. Conclusion

Although the Red-Black Tree is a notoriously difficult data structure, as long as you understand the rationale behind each operation—ensuring that from an external perspective (the number of black nodes on paths from the top of the affected part to the bottom) nothing changes—it's not that hard to remember. The most clever part is how some cases are transformed into other, easier-to-solve cases (like in deletion, turning a red sibling into a black sibling through rotation). The remaining difficulty lies mainly in the binary tree operations themselves, like pointer assignments and rotations. Implementing a Red-Black Tree in Rust adds some complexity due to manual memory management, but we successfully solved these problems using MaybeUninit + ManuallyDrop.

8. Complete Code

https://github.com/Arichy/red-black-tree-rs

A Journey From JS To Rust

Arc — Sun, 08 Jun 2025 06:00:34 +0000

This article is for developers with a background in frontend/JS/TS, introducing some of the confusions, differences, and new concepts encountered when learning Rust.

JS, with its highly dynamic and flexible scripting language features, allows us to write code with maximum freedom, doing whatever we want, basically coding without a second thought. (Do you think about memory safety and concurrency safety when writing JS? I almost never do.)

Built-in GC, so no need to consider memory management; object references can fly around freely.
Dynamic typing, so no need to consider types when assigning/modifying variables.
Extensive use of reference types, so no need to consider memory layout or distinguish between stack/heap.
Popular runtimes are mostly single-threaded + built-in event loop, so almost all concurrency issues are non-existent.

However, in the world of Rust, all the above details must be firmly kept in mind by the developer. This also leads to discomfort for JS/Python, and even Java/Go developers when learning Rust, requiring them to step far out of their comfort zones. No runtime helps us encapsulate and handle numerous low-level details anymore; only the compiler battles with us, repeatedly.

0. Pronunciation

Rust has its own unique naming conventions, some of which don't quite align with the conventions of other mainstream languages. For instance, the concept of an interface is called a trait in Rust. What's similar to a package in JS is called a crate in Rust. At the same time, Rust's design philosophy is to minimize source code characters as much as possible. Thus, function definitions use fn, not func like in Go, nor function like in JS; mutability uses mut, not the full mutable; implementing a trait uses impl, not the full implement; and strings include two types, str and String. So, to begin, let's introduce the common pronunciations within the Rust community.

Keywords/Syntax Elements

Symbol/Word	Pronunciation	Category	Notes
`str`	/stɜr/ (like “stir”)	Type	The `str` in `&str`, not “S-T-R”
`impl`	/ɪmpl/ (like “imp-l”)	Keyword	Abbreviation for implement
`dyn`	/dɪn/ or /daɪn/ (both are used)	Trait Keyword	Abbreviation for dynamic
`crate`	/kreɪt/ (like “create” without e)	Module System	A package or module unit in Rust
`trait`	/treɪt/	Interface
`enum`	/ˈiːnəm/ or /ˈɛnəm/	Enum Type
`mod`	/mɑd/ (like “mod”ify)	Module	Abbreviation for module
`mut`	/mjut/ (like mute)	Mutability	Abbreviation for mutable
`fn`	/ɛf ɛn/ (F-N)	Function	Declares a function

Types/Structs

Name	Pronunciation	Meaning
`Vec`	/vɛk/ (like “veck”) or spelled V-E-C	Vector type
`Rc`	/ɑr si/ (R-C)	Reference Counted smart pointer
`Arc`	/ɑrk/ (like “ark”)	Atomic Reference Counted

1. Basic Content: `mut`

For developers from most language backgrounds, mut is a very new and somewhat inexplicable design. When we write JS, we never consider whether a variable is mutable; by default, all variables are mutable. Even for a variable some_obj defined with const, it only means some_obj itself cannot be reassigned to another value, but the object some_obj refers to can be arbitrarily modified, such as adding/deleting/modifying fields.

However, Rust requires using mut to explicitly declare a variable as mutable, and this mutability restriction applies to the entire object tree. If a struct variable doesn't have mut, its fields cannot be modified either. There are several reasons for this:

One of Rust's design philosophies is explicitness whenever possible. For example, using mut to explicitly declare a variable as mutable means that variables without mut are immutable. When you see such a variable, you don't have to worry about its value changing anywhere later, reducing cognitive load.
Rust's Borrow Checker has a rule: For the same value T, you cannot have both a mutable reference &mut T and an immutable reference &T at the same time, so it's necessary to distinguish mutability.

2. Advanced Content: Hello World

Yes, you read that right, printing "hello world" is advanced content in Rust.

When learning other languages, we almost always start by printing "hello world". For example:

// Popular JavaScript Runtime
console.log('hello world');

// Go
fmt.Println("hello world");

// Java
System.out.println("hello world");

With one line, we can learn at least two things about the language:

How to declare strings.
How to print things.

Okay, now let's look at Rust's hello world:

println!("hello world");

It looks simple, but it hides at least four subtle yet important concepts: strings, lifetimes, fat pointers, and macros.

2.1. Strings

If you extract "hello world" into a variable, in an editor with rust-analyzer (Rust's language server, hereinafter referred to as ra) installed, it will show you the variable type:

fn main() {
  let hello_world: &'static str = "hello world";
}

The variable type is &'static str, which can be immediately confusing. The complete and accurate English translation is a reference to a string slice with a static lifetime. Let's break it down. First, this is a reference type, essentially a pointer, pointing to a type str. str is translated as string slice, and it is one type of string. Yes, Rust has many types of strings. A static lifetime means that during the program's execution, the str value this reference points to will never be destroyed and will live forever.

In the compiled binary (e.g., an ELF file on Linux) from the code above, the string "hello world" will exist in some PT_LOAD segment (on disk). When the operating system loads this binary for execution, it will load this string into the .rodata section (in memory), and then allocate a pointer on the main function's stack frame, which is the hello_world variable, pointing to this str type string "hello world".

Memory Layout
+--------------------------------------------------+
|                                                  |
|  Stack:                                          |
|  +--------------------------------------------+  |
|  |                                            |  |
|  |  hello_world: &'static str                 |  |
|  |  +---------------+---------------+         |  |
|  |  | ptr           | len           |         |  |
|  |  | 0x12345678    | 11            |         |  |
|  |  +---------------+---------------+         |  |
|  |        |                                   |  |
|  +--------|-----------------------------------+  |
|           |                                      |
|           |                                      |
|           |                                      |
|  .rodata: |                                      |
|  +--------|-----------------------------------+  |
|  |        |                                   |  |
|  |        v                                   |  |
|  |  0x12345678: "hello world"                 |  |
|  |  +---+---+---+---+---+---+---+---+---+---+---+  |
|  |  | h | e | l | l | o |   | w | o | r | l | d |  |
|  |  +---+---+---+---+---+---+---+---+---+---+---+  |
|  |                                            |  |
|  +--------------------------------------------+  |
|                                                  |
+--------------------------------------------------+

Because this "hello world" is located in the .rodata section, it will live for the entire duration of the program's execution, so the reference hello_world pointing to it has a 'static lifetime. In Rust statements, lifetimes can be elided (hidden). Therefore, in many cases, we see the type &str, which is a reference to a string slice, or simply string reference.

Why use a reference type &str instead of directly using the str type? It's because Rust requires the size of every variable to be known at compile time. Rust allocates local variables on the stack by default, and stack allocation requires a specific size, so the size of each variable in a stack frame must be known. However, the size of the str type is unsized (not known at compile time) because you cannot know the size of an arbitrary str type string at compile time. The &str mentioned above points to a static "hello world" string, so its length is known, but &str can also point to dynamic strings whose size can change arbitrarily at runtime. Therefore, the size of str cannot be determined at compile time, so we can only use the &str reference type, because the size of a reference type is determinable.

From the memory layout diagram, we can see that &str is not just a simple pointer; it also contains a length field len, used to indicate the length of the str it points to. In C, strings are terminated by a special character \0, so their length doesn't need to be stored explicitly. However, Rust's mechanism doesn't use \0, so a length field is needed. This type of pointer that carries extra information is called a fat pointer. So, &str has a fixed size of 2 usizes. usize is an integer type that is platform-dependent, representing the size of a pointer on the current platform. On a MacBook with Apple Silicon, this size is 64 bits, or 8 bytes. Therefore, an &str is 16 bytes.

Having finally introduced str and &str, let's now introduce String. String is a type that is allocated on the heap because it is essentially a Vec<u8>, and Vec is allocated on the heap.

fn main() {
    let mut hello_string = String::from("hello");
}

Memory Layout
+--------------------------------------------------+
|                                                  |
|  Stack:                                          |
|  +--------------------------------------------+  |
|  |                                            |  |
|  |  hello_string: String                      |  |
|  |  +---------------+---------------+---------+  |
|  |  | ptr           | len           | capacity |  |
|  |  | 0xABCDEF      | 5             | 5        |  |
|  |  +---------------+---------------+---------+  |
|  |        |                                   |  |
|  +--------|-----------------------------------+  |
|           |                                      |
|           |                                      |
|           |                                      |
|  Heap:    |                                      |
|  +--------|-----------------------------------+  |
|  |        |                                   |  |
|  |        v                                   |  |
|  |  0xABCDEF:                                |  |
|  |  +---+---+---+---+---+                     |  |
|  |  | h | e | l | l | o |                     |  |
|  |  +---+---+---+---+---+                     |  |
|  |                                            |  |
|  +--------------------------------------------+  |
|                                                  |
+--------------------------------------------------+

Let's ignore the len and capacity of hello_string for now; we'll discuss them later when we introduce Vec. A String type variable allocates memory on the heap to store the string and then uses a pointer on the stack to point to it. Because the underlying data of String is allocated on the heap, its length is naturally variable. When we need a mutable string, we use String.

// Common ways to create a String, with 1 and 2 being the most used
let s = "hello".to_string(); // Call the to_string method of &str
let s = String::from("hello"); // Call the from method of the From<&str> trait implemented by String
let s: String = "hello".into(); // Because String implements From<&str>, &str automatically implements Into<String>. However, since &str implements multiple Into traits, the type of s needs to be explicitly declared.
let s = "hello".to_owned(); // Call the to_owned method in the ToOwned trait implemented by str
let s = String::new(); // Create an empty string
let s = String::default(); // Call the default method of the Default trait implemented by String, creating an empty string

// Modify String
let mut s = "hello".to_string(); // s: "hello"
s.push_str(" world"); // s: "hello world"

&str and String are the two most commonly used string types in Rust, but Rust also provides other string types: PathBuf vs Path, OsString vs OsStr, etc. These are essentially no different from String vs &str but are used in specific domains. For example, Path is a wrapper around OsStr, and OsStr is a wrapper around [u8], but specifically for path-related operations, such as arguments to file reading functions. Thus, they will have additional specific methods like is_dir, is_absolute, etc.

This is also one of Rust's design philosophies: values that are essentially the same type will be wrapped into different types in different contexts. A classic example is time points and time durations.

In JS, we use number to represent timestamps, i.e., a point in time. We also use number to represent a duration of time:

// Represents a timestamp 1000ms in the future

const now: number = Date.now();
const duration_ms: number = 1000;
const then: number = now + duration_ms;

The problem with this is that when I get a variable of type number, it's hard to determine what this variable actually represents. It could be a time point, a duration, age, mass, physical attack, or magic penetration.

In Rust, although they are essentially integer-like data, they are wrapped into different types in different scenarios:

use std::time::{Duration, Instant};
use std::thread;

let now: Instant = Instant::now(); // Please note Instant::now does not return the current wall-clock time
let duration_ms: Duration = Duration::from_millis(1000);
let then: Instant = now + duration_ms;

This way, when I call a function like thread::sleep that expects a Duration, I won't pass an Instant or other integer types.

FYI, JS's new time module Temporal also introduces the distinction between Duration and Instant.

2.2. Macro

You must be curious why some "function calls" have an exclamation mark at the end, while others don't. For example, "hello".to_string() doesn't have an exclamation mark, but println!() and write!() do. This is because println and write here are not functions, but declarative macros.

A declarative macro is a type of macro that uses a mechanism similar to regular expression matching to match internal code and then transform it into another set of code. Since the code println ultimately transforms into is special compiler-handled code, we'll use vec!, a declarative macro for initializing a vector with an arbitrary number of elements, as an example.

macro_rules! vec {
    () => (
        $crate::vec::Vec::new()
    );

    ($elem:expr; $n:expr) => (
        $crate::vec::from_elem($elem, $n)
    );

    ($($x:expr),+ $(,)?) => (

        <[_]>::into_vec(
            $crate::boxed::Box::new([$($x),+])
        )
    );
}

A declarative macro defines multiple branches, each representing a match. At the beginning of compilation, matching is performed. When a branch is matched, the code corresponding to that branch replaces the original code. For example:

let vec = vec![1, 2, 3];
// Will be replaced with
let vec = <[_]>::into_vec(#[rustc_box] ::alloc::boxed::Box::new([1, 2, 3]));

Since declarative macros are quite complex, we won't go into too much detail here. Just know that they expand and replace original code at the beginning of compilation. So, the question is, why are println! and vec! designed as macros instead of directly providing println and vec functions? Because the number of arguments for a Rust function must be fixed. Rust also doesn't support function overloading. However, for println!, the number of arguments is not fixed; it depends on how many slots need to be inserted and replaced in the template string. Similarly, the number of initial elements vec! accepts cannot be fixed. Therefore, these two are designed as macros, expanding at the beginning of compilation to call another function with a fixed number of arguments.

Rust macros are divided into the following categories:

declarative macros
procedural macros
- function-like macros
- derive macros
- attribute macros

Here, we'll only briefly introduce procedural macros without going into depth. The three types of procedural macros are essentially functions that take TokenStream (representing a piece of input Rust code) as an argument and return a TokenStream (representing a piece of output Rust code). At the beginning of compilation, this function is executed, and then the Rust code corresponding to the return value is generated.

Declarative macros perform a match, hence the name "declarative." I declare several branches; if you match one, I perform the replacement. Procedural macros execute a function, hence the name "procedural." Beginners often fall into the trap of seeing macro invocations like println!("hello") that look like function calls and assume they are function-like macros. This is incorrect. Declarative and procedural macros are distinguished by how they operate on the input code.

FYI, you can install the cargo-expand tool using cargo install expand. After installation, you can use the cargo expand command to view the expanded results of some macros.

3. Array vs Vec

In JS, Array is probably one of the most used data structures, if not the most. We are already familiar with various operations on arrays, including creation, and inserting/deleting elements at any position. Unfortunately, in Rust, the array type is [T; N], where T is the element type and N is the number of elements, and the number of elements must be determined at compile time. This is quite restrictive; the array length must be fixed when writing the code, making its flexibility very limited. This also means the use cases for array types are very limited; even a basic function for iterating and printing cannot take an array as a parameter in a generic way (without knowing its size).

So, in Rust, the Vec (vector) struct is used more often, which is also the underlying data structure for the String type. Vec is similar to JS's Array; its length is variable, and you can play with it however you want. In the memory layout diagram for String, we saw that Vec consists of three parts:

ptr: A pointer to the actual data on the heap, pointing to the first element in the vec.
len: The current length of the vec, i.e., the current number of elements.
capacity: The current capacity of the vec.

The first two are relatively easy to understand, but capacity is a bit puzzling. Simply put, capacity is the maximum number of elements the current vec can hold, and capacity is always >= len. When capacity == len, the vec is full. At this point, if you execute methods like vec.push to insert elements, the vec will first reallocate (grow), which means allocating a new block of memory with a larger capacity (usually current capacity * 2), then moving all its existing elements to the new location, and then inserting the new element. Of course, this reallocation might happen in place, meaning the starting point of the new memory is the same as the current memory's starting point, in which case the elements don't need to be moved. Therefore, strictly speaking, the time complexity of the push method is not necessarily O(1); it can be O(n) when reallocation occurs.

At this point, we can explain the reason for the rule: "For the same value T, you cannot have both a mutable reference &mut T and an immutable reference &T at the same time." Consider the following code:

let mut v = vec![1, 2, 3, 4]; // 1

let v_shared_ref = &v; // 2. First, get a shared reference (immutable reference)
v.push(5); // 3. Then, get a mutable reference; the push method automatically creates a mutable reference

println!("{:?}", *v_shared_ref); // ❌ 4. Using the shared reference created in 2

At step 3, an immutable reference and a mutable reference (implicitly taken by push) would exist simultaneously (if allowed by the compiler, which it isn't for this specific sequence). This violates the rule. The consequence (if the compiler didn't prevent it) could be that in step 3, because the vec reallocates, the entire vec is moved to a newly allocated address, while the original v_shared_ref still points to the old address, becoming a dangling pointer. In step 4, dereferencing it would cause undefined behavior. Memory safety would be compromised.

4. Enum and Pattern Matching

enum in TS is not a very good design, has many problems, is not used much in actual development, and therefore is not given much importance.

However, in Rust, enum is an extremely important structure. The reason is simple: Rust does not have union types; Rust only has sum types (which enums provide). So Rust can only use enums to achieve the effect of union types. Moreover, Rust's enums are much more powerful than those in other languages because they support carrying data (variants can have associated types), in conjunction with Rust's own pattern matching language feature.

Suppose we want to implement a printAdd1 function whose parameter can be a string or a number. If it's a string, print the result of string + "1". If it's a number, print the result of number + 1. In TS, we would write:

function printAdd1(val: string | number) {
  if (typeof val === 'string') {
    console.log(`${val}1`);
  } else {
    console.log(val + 1);
  }
}

But in Rust, we need to use an enum:

enum StringOrNumber {
    String(String),
    Number(i32),
}

fn print_add_1(val: StringOrNumber) {
    match val {
        StringOrNumber::String(s) => {
            println!("{}1", s);
        }

        StringOrNumber::Number(n) => {
            println!("{}", n + 1);
        }
    }
}

Enums are ubiquitous in Rust.

4.1. Potentially Null Values: `Option<T>`

Rust does not have null. So, to express a variable T that might have a value or might be empty, an enum is needed: Option<T>.

For example, to implement a division function, in TS we would do this:

function divide(a: number, b: number): number | null {
  if (b === 0) {
    return null;
  }

  return a / b;
}

const result = divide(userInput1, userInput2);

if (result === null) {
  // handle null
}
// handle result

In Rust, we need:

fn divide(a: f64, b: f64) -> Option<f64> {
  if b == 0.0 {
    None
  } else {
    Some(a / b)
  }
}

let result = divide(user_input_1, user_input_2);

match result {
  Some(result_val) => {
    // handle result_val
  }

  None => {
    // handle null
  }
}

4.2. Error Handling: `Result<T, E>`

For the divide function above, we can also use Result<T, E> as the return value.

fn divide(a: f64, b: f64) -> Result<f64, String> {
    if b == 0.0 {
        Err("0 could not be the denominator".to_string())
    } else {
        Ok(a / b)
    }
}

let result = divide(2.0, 1.0);

match result {
    Ok(result_val) => {
        // handle result_val
    }

    Err(reason) => {
        // handle error
    }
}

E itself has no restrictions and can be any type. However, E will usually be a type that implements the Error trait.

4.3. `unwrap`

If you find Option and Result too cumbersome, and you just want to simply read file content without writing a bunch of match statements to handle the result, then unwrap will bring you back to your comfort zone for a while.

// read a file in JS
import { readFileSync } from 'fs';
const content = readFileSync('/path/to/some_file', 'utf-8');
console.log(content);

// read a file in Rust
use std::fs;
let content = fs::read_to_string("/path/to/file").unwrap();
println!("{content}");

unwrap is a method available on both Option and Result.

For Option<T>, it returns the T wrapped in Some(T). If it's None, it will panic.
For Result<T, E>, it returns the T wrapped in Ok(T). If it's Err(E), it will panic.

In a formal production environment, unwrap should only be used when you are absolutely sure there will be no problem, to simplify code.

5. Trait

Another design characteristic of Rust is its unconventional naming. In other languages, this concept is almost always called interface, but Rust names it trait. The concepts are very similar, but traits are more powerful, arguably the cornerstone of the entire Rust program structure or ecosystem. At all times, we need to think about problems in terms of traits, which is another major point of discomfort for JS developers. In JS, when using third-party libraries, we basically only focus on the functions/classes/objects they provide and then directly call existing methods. But in Rust, we also need to pay attention to traits. When using third-party crates, often we will only use traits, making our own structs implement the traits they provide, and then use their functionality.

A trend in the programming world today is to reduce object-oriented programming. Newer languages like Go/Rust have almost completely abandoned OOP, no longer having concepts like class, object, extends, etc. Although JS simulates classes through prototypes, the current community trend is also abandoning OOP, a typical example being React using function components + hooks (functional programming + composition over inheritance thinking) to replace class components.

Rust's traits are the best embodiment of composition over inheritance. For a struct, we don't judge what methods it has by thinking about its inheritance relationships, but by thinking about which traits it implements. Our thinking should include:

My struct needs to implement certain methods, so these methods are likely already defined in an existing trait in the standard library, so I need to make my struct implement this trait.
My function may need to operate on multiple types, but these types must satisfy certain common conditions, so I need to constrain the function's generic parameters to satisfy one or more traits.

Everything in Rust is implemented around traits. For example, basic printing: in JS, we can use console.log to print anything, but not in Rust. This is because in JS, there are many things we don't think about, such as whether the thing to be printed is serializable and in what format it should be serialized. The JS runtime solves these problems for us. But Rust doesn't solve them for us; we need to think about them ourselves.

println!("{}", some_variable);
println!("{:?}", some_variable);

Both methods above can print some_variable. In the first method, some_variable is required to implement the std::fmt::Display trait. In the second method, it is required to implement the std::fmt::Debug trait. The difference is that Display is generally a human-readable format, while Debug is a format for programmers to easily debug. For example, when printing a string, Display will only print the string itself, while Debug will additionally print the surrounding double quotes.

struct Coordinate {
  x: i32,
  y: i32,
}

let c = Coordinate {
  x: 1,
  y: 2,
};

println!("{}", c); // Error: Coordinate does not implement Display
println!("{:?}", c); // Error: Coordinate does not implement Debug

Both print statements above will error because Coordinate implements neither Display nor Debug. Generally, we use #[derive(Debug)] to automatically implement Debug for custom structs, facilitating debugging during development. The prerequisite for automatically deriving Debug is that all fields within the struct must have already implemented Debug. For example, x and y in Coordinate are i32, which both implement Debug, so Debug can be derived. However, Display cannot be automatically derived; if needed, it must be implemented manually.

#[derive(Debug)]
struct Coordinate {
    x: i32,
    y: i32,
}

impl std::fmt::Display for Coordinate {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "({}, {})", self.x, self.y)?;

        Ok(())
    }
}

let c = Coordinate { x: 1, y: 2 };
println!("{c}"); // (1, 2)
println!("{c:?}"); // Coordinate { x: 1, y: 2 }

From the results, we can also see that Display prints for humans, while Debug prints for programmers.

6. Closures vs Functions

Closures are a concept not given much importance in JS. When we define functions, we rarely think about whether they are closures. The word "closure" doesn't appear much in the JS community. But in Rust, closures are a very important concept that needs to be memorized separately.

Simply put, a closure is essentially a struct that captures external variables; it is not a function. In Rust, all variables need to have their storage location clearly determined. The so-called "captured variables" also need to be stored somewhere, so closures are compiled into structs, storing the captured variables within the struct.

let to_add = 1;
let f = |i: i32| {
    let tmp = 0;
    tmp + i + to_add
};

let result = f(42);

The above code will be compiled into something like this:

// Conceptual representation
struct F_Closure {
    to_add: i32,
}

impl FnOnce<(i32,)> for F_Closure {
    type Output = i32;
    extern "rust-call" fn call_once(self, args: (i32,)) -> Self::Output {
        let tmp = 0;
        tmp + args.0 + self.to_add
    }
}

impl FnMut<(i32,)> for F_Closure {
    extern "rust-call" fn call_mut(&mut self, args: (i32,)) -> Self::Output {
        let tmp = 0;
        tmp + args.0 + self.to_add
    }
}

impl Fn<(i32,)> for F_Closure {
    extern "rust-call" fn call(&self, args: (i32,)) -> Self::Output {
        let tmp = 0;
        tmp + args.0 + self.to_add
    }
}

let f = F_Closure { to_add };

let result = f.call((42,));

A Rust closure is a struct that implements the FnOnce/FnMut/Fn traits. Captured variables are stored in the struct, and when called, the corresponding call_once/call_mut/call method is invoked.

FnOnce: Receives self, calling it consumes self, so it can only be called once.
FnMut: Receives &mut self, calling it allows modification of the struct (i.e., captured variables), can be called multiple times.
Fn: Receives &self, calling it does not allow modification of the struct, can be called multiple times.

The relationship between these three traits is: Fn is a sub-trait of FnMut, which is a sub-trait of FnOnce. This is ordered from most to least restrictive in terms of what the closure body can do. Fn is the most restrictive, only allowing immutable access to captured variables. FnOnce is the least restrictive, allowing anything.

Importantly, Rust closures are complex types, so ra will tell you the type of f is impl Fn(i32) -> i32, indicating that f is a struct that implements Fn, but its specific name is unknown. Because Rust generates a unique struct for each closure, no two closures can have the same type, even if their parameter lists, internal implementations, and return values are identical.

6.1. Capture by Reference vs Capture by Ownership

Rust can capture external variables by reference or by ownership.

let mut s = "hello".to_string();
let f = || {
    let b = s; // s is moved here
    b.push_str(" world");
};
f();

println!("{s}"); //  ❌ s has been moved into f

The f above implements FnOnce because when f is defined (or rather, when it would be called), s is moved into the f struct. When called, it's moved into the function body to b. Since b is a local variable within the function, it will be destroyed after the call, so this function can only be called once, consuming the entire struct.

let mut s = "hello".to_string();
let mut f = || { // f is inferred as FnMut
    s.push_str(" world"); // s is mutably borrowed here
};
f();

println!("{s}"); // ✅ s was not moved to f, so it can still be accessed here

Although s is used inside f above, because push_str only requires &mut String, only &mut s is captured. s remains accessible afterwards.

let mut s = "hello".to_string();
let mut f = move || {
    s.push_str(" world"); // s is owned by the closure now
};

f();
println!("{s}"); // ❌ s has been moved into f

By using the move keyword, we tell the compiler that f will capture ownership of s, so s will be moved into the f struct and is no longer accessible afterwards.

In concurrent programming, move is almost always used. For example, when creating a thread using thread::spawn, you must use move to move all captured external variables into the closure, passing them to the new thread, because the execution order and timing of the two threads are completely indeterminate. The main thread might finish before the new thread completes, thereby destroying variables on its own stack.

For regular functions defined with fn, they have specific types, e.g., fn(i32) -> i32. Therefore, multiple functions can be of the same type, and all regular functions implement FnOnce + FnMut + Fn. In other words, all regular functions can be used as closures.

7. Multithreading and Async

Due to the inherent difficulty of multithreading and async, this article will not describe them in excessive detail, only introducing some of the most basic concepts.

Multithreading: Start multiple threads using methods in the thread module.
Async: Similar to JS's async/await.

7.1. Multithreading

Suitable for CPU-bound tasks, can be processed in parallel. This point is often a blind spot for JS developers because popular JS runtimes only provide single-threaded access to developers, lacking the capability for true parallelism.

7.2. Async

Suitable for I/O-bound tasks, can be processed concurrently. When JS developers first encounter Rust's async/await, they will feel both familiar and strange. The familiar part is that the syntax is basically the same: async defines an asynchronous function, and await waits for an asynchronous function to return, just that in JS await is placed before the asynchronous call, while in Rust it's placed after. However, the strange parts are rather perplexing:

The main function cannot be async. In JS, due to the infectious nature of async/await, if the main function cannot be async, what about all the await calls inside it?
I've searched the entire standard library and haven't found a single async fn. Whether it's reading files or network requests, there isn't a single async fn. The familiar const content = await readFile("xxx") seems impossible to write.

This again comes back to Rust's design philosophy. The Rust standard library does not provide any asynchronous implementation, nor does it provide any asynchronous runtime; these are all left to third-party implementations in the community. Rust official only provides the async/await syntactic sugar, compiling it at the language level into synchronous-looking code (centered around the Future trait), but how to actually execute these futures, Rust official doesn't handle; you need to provide a runtime yourself to schedule them.

Currently, the de facto standard async runtime is tokio. Beginners can just use tokio without much thought.

use tokio::fs::read_to_string;

#[tokio::main]
async fn main() {
    let content_result = read_to_string("/path/to/file").await;
    match content_result {
        Ok(content) => {
            // handle content string
        }
        Err(err) => {
            // handle error
        }
    }
}

Tokio provides a complete asynchronous ecosystem, including a scheduler, event loop (I/O, timers, etc.), asynchronous methods (fs, net, channel, etc.), and other features. At this point, you should again have the feeling that the reason we write JS so comfortably is that these contents are provided by the underlying runtime. For example, macro/micro tasks in JS are essentially tokio's scheduler. Node.js's event loop also has a corresponding implementation in tokio.

8. Forgetting Object-Oriented Programming

Rust is not an object-oriented language, so when learning it, it's best to set aside an object-oriented mindset (of course, strictly speaking, JS isn't an object-oriented language either, as it lacks classes). Rust does not have classes or inheritance, but it does borrow some features from OOP. For example, it implements encapsulation using struct + impl + pub visibility control, and it achieves polymorphism through various means.

8.1. The Essence of Method Calls

In Rust, there are technically no methods; all methods are just regular functions.

let mut nums = vec![1, 2, 3];

nums.push(4);
// is essentially
Vec::push(&mut nums, 4);

Essentially, every method call creates a reference to the instance (or passes the instance itself) based on the method's self type (self, &self, or &mut self), passes it as the first argument to the function, and then passes the remaining arguments. This understanding is very helpful when wrestling with lifetimes. Explicitly writing out &mut xx makes it clearer that a mutable reference is being created at that point, which aids in reasoning about its lifetime.

8.2. Generics for Parametric Polymorphism

Parametric polymorphism refers to a function's ability to perform the same operation on different types. Rust uses generics to achieve parametric polymorphism, performing monomorphization on generic functions at compile time. Monomorphization means that for every type that calls the generic function, a unique function specific to that type is generated.

fn get_first<T>(slice: &[T]) -> &T {
    &slice[0]
}

let nums = vec![1, 2, 3];
let strings = vec!["1".to_string(), "2".to_string(), "3".to_string()];

let first_num = get_first(&nums);
let first_string = get_first(&strings);

The code above will be monomorphized into two different functions:

fn get_first_i32(slice: &[i32]) -> &i32 {
    &slice[0]
}

fn get_first_String(slice: &[String]) -> &String {
    &slice[0]
}

let first_num = get_first_i32(&nums);
let first_string = get_first_String(&strings);

As you can see, the calls for &nums and &strings invoke two different functions. The advantage of this is extreme performance with zero runtime overhead, as the compiler knows exactly which function to call at compile time. The disadvantage is that if many different types use this function, generating a function for each type can lead to a larger binary bundle size.

Generics implement static dispatch because the specific function being called is known statically at compile time. This might be unfamiliar to JS programmers because TypeScript generics are erased at compile time, so no static dispatch occurs.

8.3. Trait Objects for Subtype Polymorphism

Subtype polymorphism means that an object of a subtype can be used as if it were of its parent type. When a method is called through a reference to the parent type, the method on the subtype is called preferentially. Since Rust has no classes and inheritance, there is no parent-child relationship. Instead, this relationship is between a type and a trait. If a function doesn't care about the concrete type of its parameter but only that it implements a certain trait, it can use a trait object.

    fn get_string(input: Box<dyn ToString>) -> String {
        input.to_string()
    }

    let res1 = get_string(Box::new("123"));
    let res2 = get_string(Box::new(456));

The dyn ToString above is a trait object, representing any type that implements the ToString trait. Since the concrete type is unknown, its size is also unknown. Rust requires every parameter/variable to have a concrete size, so it must be placed within a pointer type. The most common one is Box, or you can use a reference &dyn ToString. Inside the get_string function, the input has lost its concrete type, becoming a Box<dyn ToString> trait object instead. Therefore, you can only call methods from the ToString trait, such as to_string.

The requirement above can also be met with generics, but some scenarios exclusively require trait objects. A classic example is collection types like arrays, slices, or Vec:

fn get_strings<T: ToString>(input: &[Box<T>]) -> Vec<String> {
    let mut vec = vec![];
    for item in input {
        vec.push(item.to_string());
    }

    vec
}

let res = get_strings(&[Box::new("123"), Box::new(456)]);

The code above will produce an error:

error[E0308]: mismatched types
  --> src/main.rs:99:46
   |
99 |     let res = get_strings(&[Box::new("123"), Box::new(456)]);
   |                                              ^^^^^^^^^^ expected `&str`, found integer
   |
   = note: expected type `Box<&str>`
              found type `Box<{integer}>`

This is because all elements in a collection type must have the exact same type, but Box<&str> and Box<i32> are clearly different types and cannot be placed in the same slice. This is where trait objects become necessary:

fn get_strings(input: &[Box<dyn ToString>]) -> Vec<String> {
    let mut vec = vec![];
    for item in input {
        vec.push(item.to_string());
    }

    vec
}

let res = get_strings(&[Box::new("123"), Box::new(456)]);

Now, the element type of this slice is Box<dyn ToString>, which is a single, consistent type. This scenario becomes even more apparent with closures, as each closure has a unique, unnameable type. If you want to store them in a collection, you must use a trait object, such as Box<dyn Fn(i32, i32) -> i32>.

Trait objects implement dynamic dispatch because the concrete function for item.to_string is not known at compile time. At compile time, a structure called a vtable is created and placed in a read-only data segment (like the .rodata section). Then, at runtime, this vtable is used to find the actual function to call and execute it. The process is as follows:

trait Animal {
    fn speak(&self) -> String;
    fn number_of_legs(&self) -> u8;
}

struct Dog;
impl Animal for Dog {
    fn speak(&self) -> String { "Woof!".to_string() }
    fn number_of_legs(&self) -> u8 { 4 }
}

struct Cat;
impl Animal for Cat {
    fn speak(&self) -> String { "Meow!".to_string() }
    fn number_of_legs(&self) -> u8 { 4 }
}

fn main() {
    // This conversion is the key moment that triggers the creation and use of the vtable!
    let dog_animal: Box<dyn Animal> = Box::new(Dog);
}

1. Static Construction at Compile Time

When the compiler processes the line let dog_animal: Box<dyn Animal> = Box::new(Dog);, it performs the following series of operations:

1.1. Identify the trait-type Combination
The compiler recognizes a conversion from the concrete type Dog to the trait object dyn Animal. It locks onto this combination: (Dog, dyn Animal).

1.2. Find and Analyze the Trait and impl
The compiler looks at the Animal trait definition. It knows that any dyn Animal must be able to call the speak and number_of_legs methods.

1.3. Construct the Vtable's Memory Layout
The compiler determines the structure of the vtable for the dyn Animal trait object. It is essentially an array (or struct) of function pointers, with a layout roughly like this:

// This is pseudo-code describing the internal structure of the vtable
struct VTableForAnimal {
    // 1. Pointer to the destructor (for correctly dropping the object)
    void (*_drop_in_place)(void*);

    // 2. The object's size and alignment
    size_t size;
    size_t align;

    // 3. Function pointers to each method in the Trait
    String (*speak)(void*); // Points to Dog::speak
    u8 (*number_of_legs)(void*); // Points to Dog::number_of_legs
}

Note that the vtable contains not only pointers to trait methods but also three important pieces of metadata: a destructor pointer, size, and alignment. This enables Box<dyn Animal> to know how to correctly free the memory of the "type-erased" object it points to.

1.4. Create and Store a Static Vtable Instance
The compiler creates a global, static, read-only vtable instance for the (Dog, dyn Animal) combination. This vtable instance is placed in the read-only data section (e.g., the .rodata section) of the final executable file. It looks something like this:

// Pseudo-code: The compiler generates such a constant in the .rodata section
const VTableForAnimal VTABLE_DOG_AS_ANIMAL = {
    .drop_in_place = &drop_dog,      // Points to Dog's destructor logic
    .size = size_of::<Dog>(),        // The size of the Dog type (which is 0 here)
    .align = align_of::<Dog>(),      // The alignment of the Dog type
    .speak = &Dog::speak,            // Points to the machine code address of the Dog::speak function
    .number_of_legs = &Dog::number_of_legs // Points to the machine code address of the Dog::number_of_legs function
};

This vtable is not created for each Dog object. Instead, all Dog types share the same single vtable instance when used as a dyn Animal.
Similarly, the compiler would create another separate, static vtable for the (Cat, dyn Animal) combination: VTABLE_CAT_AS_ANIMAL.

2. Pointer Combination at Runtime

After all the above preparations are completed at compile time, what happens at runtime becomes very simple.

When the line let dog_animal: Box<dyn Animal> = Box::new(Dog); is executed at runtime:

2.1. Box::new(Dog) allocates memory on the heap to store a Dog instance.

2.2. During the Dog -> dyn Animal conversion, a fat pointer is created.

2.3. This fat pointer consists of two parts:
_ Data Pointer -> Points to the address of the Dog instance on the heap.
_ Vtable Pointer -> Points to the address of the VTABLE_DOG_AS_ANIMAL that the compiler created and stored in the read-only data section.

    STACK                                      HEAP                                     .RODATA (Read-Only Data)
+------------------------+                     +-----------------+                    +============================+
| dog_animal             |                     | Dog Instance    |                    | VTABLE_DOG_AS_ANIMAL       |
| (Box<dyn Animal>)      |                     | (on the heap)   |                    | (static, read-only)        |
| +--------------------+ |                     +-----------------+                    |----------------------------|
| | data_ptr      | ---|---------------------->| (Dog's fields)  |                    | drop_ptr      | ---------> | (drop code for Dog)
| +--------------------+ |                                                            | size          | (e.g. 0)   |
| | vtable_ptr    | ---|------------------------------------------------------------->| align         | (e.g. 1)   |
| +--------------------+ |                                                            | speak_ptr     | ---------> | Dog::speak() code
+------------------------+                                                            | num_legs_ptr  | ---------> | Dog::number_of_legs() code
                                                                                    +============================+
                                                                                    | VTABLE_CAT_AS_ANIMAL       |
                                                                                    | (another static vtable)    |
                                                                                    | ...                        |
                                                                                    +============================+

When dog_animal.speak() is called:

2.4. The runtime follows the vtable_ptr from dog_animal to find VTABLE_DOG_AS_ANIMAL.

2.5. It looks up the function pointer corresponding to speak_ptr within the vtable.

2.6. It follows the data_ptr from dog_animal to find the address of the Dog instance and passes it as the &self argument.

2.7. It calls the function pointed to by the function pointer, which is Dog::speak(&dog_instance).

8.4. Traits for Ad-Hoc Polymorphism

Ad-hoc polymorphism refers to the ability of a single operation to execute different logic depending on the types of its operands. This is different from parametric polymorphism, where the same operation is performed on different types. In ad-hoc polymorphism, different operations are performed on different types. The most typical example is function overloading, but Rust does not support function overloading.

Rust achieves ad-hoc polymorphism through traits. You can implement the same trait for different types, but with different specific implementations.

Summary

From the flexibility and freedom of JS to the rigor and restraint of Rust, learning Rust is like transitioning from "doing whatever you want" to "walking on thin ice." JS runtimes shield us from low-level details like memory management and concurrency safety, allowing us to focus on rapidly implementing features. Rust, however, requires developers to confront these challenges directly, ensuring code safety and performance through strict compile-time checks.

This shift in mindset, though initially uncomfortable, will lead to more robust and efficient coding abilities once adapted. Rust's features like ownership, borrow checking, pattern matching, and traits are not just the essence of the language's design but also manifestations of modern programming paradigms. They compel you to organize code more clearly, reduce hidden bugs, and enhance program reliability.

If you're used to JS's "soaring freely," Rust might feel restrictive, but it's precisely this restriction that will ultimately lead you to write more stable and secure programs. Rust isn't about writing faster; it's about writing correctly.

Pin in Rust: The Why and How of Immovable Memory

Arc — Mon, 05 May 2025 10:51:53 +0000

Pin is a complicated concept for Rust beginners because it's too abstract. But is's also the cornerstone of async Rust. Now I'm going to introduce Pin in following parts:

Why Pin is needed
What is Pin
The essential of Pin, implement a basic MyPin

Why Pin is needed

The danger Self-Referential struct

In Rust, there's a particularly dangerous kind of data structure called a self-referential structure. This refers to a struct that contains a reference or pointer to another field within itself.

An object can move in memory freely, but its internal pointer will not be updated accordingly, still pointing to the old address, breaking the structure, causing undefined behavior.

For example (I'll use pointer instead of reference to avoid lifetime, for simplicity):

#[derive(Debug)]
struct SelfRef {
    v: String,
    ptr: *const String,
}


impl SelfRef {
    pub fn new(v: String) -> Self {
        Self {
            v,
            ptr: std::ptr::null(),
        }
    }

    pub fn correct_ptr(&mut self) {
        self.ptr = &self.v;
    }
}

fn create_self_ref(v: String) -> SelfRef {
    let mut res = SelfRef::new(v);
    res.correct_ptr();
    res
}

fn main() {
    let a = create_self_ref("hello".to_string());

    println!("{}", unsafe { &*a.ptr });
}

In SelfRef, the ptr will point to v, so it's self-referential. And the code will crash because we set the ptr to the address of v in create_self_ref, now everything goes well. But when the function returns res to main, res would move to another piece of memory. However, ptr did not get updated, still pointing to the old address which has been freed. So the program crashed when dereferencing ptr.

We may write very few self-referential structs, but in async they're ubiquitous. If you're not familiar with async, here is a basic introduction.

The essential of async/await

async/await is a syntax sugar. It will be compiled to a state machine.

async fn self_referential() -> i32 {
    let x = String::from("hello");
    let x_ref = &x; // create a reference to x

    // put an await to get a state machine
    dummy_future().await;

    // use the reference after await, which will introduce a self-referential future
    x_ref.len() as i32
}

would be compiled to pseudo code:

enum SelfReferentialFuture {
    // initial state
    Start,
    // waiting dummy_future to be ready
    WaitingOnDummy {
        x: String,
        x_ref: *const String,
        dummy: DummyFuture,
    },
    // final state
    Done,
}

When a reference is used across an await, a self-referential future will appear, because all these variables must be stored inside the future. If the future moved during poll, any internal reference would become invalid, leading to undefined behavior.

So that's why we need Pin to prevent futures from moving, and why the poll function takes a Pin<&mut impl Future> instead of &mut impl Future:

fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>

Pin/Unpin

First, it's important to clarify one point. For a value with type T, if you want to move it, you must have a &mut T. If you have no way to get a &mut T, you're not able to move it.

Then let's go through Pin/Unpin.

pub struct Pin<Ptr> {
   pub __pointer: Ptr,
}

pub auto trait Unpin {}

Pin is a struct with a pointer type field Ptr. Pointer type means it has Deref trait, such as Box, Rc, Arc, &T, &mut T, etc. It must store a pointer to T instead of direct T, because if T is store directly in Pin, when Pin moves, T will move together. But if Pin stores a pointer, it's totally fine for the pointer to move around with Pin.

Unpin is an auto trait. If all the fieldsof a struct implement Unpin, then the struct itself will implement Unpin automatically. Everything is Unpin by default, including our SelfRef.

Unpin means the struct is not sensitive to being moved. It does not care if it's moved at all. Unpin does not mean if it's movable, or not movable. In Rust, every type could move. Unpin means even if it's wrapped by Pin, user could still get &mut T by Pin::get_mut and move it. Only types with !Unpin is not allowed to move by the type system of Rust.

Obviously SelfRef is sensitive to being moved, so we need to remove Unpin for it manually.

In nightly Rust, we could do like this:

impl !Unpin for SelfRef{}

But impl !Trait is still an unstable feature. In stable Rust, we need to use a marker field:

struct SelfRef {
    v: String,
    ptr: *const String,
    _pin: PhantomPinned, // marker
}

PhantomPinned is a struct provided by std::marker. It has implemented !Unpin internally, so SelfRef will not implement Unpin.

Pin<&mut T> or Pin<Box<T>> means either

T will not move
T: Unpin

If T: Unpin, it does not care if it's moved, and the protection by Pin<&mut T> is meaningless. It's useful when we explore methods from Pin.

The essential of Pin

The essential of Pin is rather simple. It has no any magic. Imagine if we don't have Pin from std. For SelfRef, we hope it could not move. How could we achieve that? The easiest way is to put it to heap, then hide it inside another struct.

// crate 1
pub struct MyPin<Ptr> {
    ptr: Ptr,
}

impl<Ptr: Deref> MyPin<Ptr> { // Ptr should be a pointer type
    pub fn new(ptr: Ptr) -> Self {
        Self { ptr }
    }
}

// crate 2
let sr = SelfRef::new("hello".to_string());
let mut boxed = Box::new(sr);
boxed.correct_ptr();
let my_pinned_sr = MyPin::new(boxed);

That's all. We're done. When you type my_pinned_str. in editor like VSCode, there is no hint. MyPin has no public fields or methods. sr is hidden in MyPin, and we have no way to access it, so it cannot move.

Please attention that we called boxed.correct_ptr(), because Box::new(sr) would move sr from stack to heap. We need to fix the pointer after the move.

The basic version has indeed achieved the prevention of movement, but it's sort of meaningless. We don't have access to sr at all. Is there any way to access it? Just like those smart pointers, we could implement Deref for it.

impl<Ptr: Deref> Deref for MyPin<Ptr> {
    type Target = Ptr::Target;
    fn deref(&self) -> &Self::Target {
        self.ptr.deref()
    }
}

impl SelfRef {
    pub fn say_string(&self) {
        println!("My value is: {}", self.v);
    }

    pub fn correct_ptr(&mut self) {
        self.ptr = &self.v;
    }
}

// duplicate code omitted
my_pinned_sr.say_string();
println!("{}", my_pinned_sr.v);

Now we could access fields of my_pinned_str, and methods with &self. We only implemented Deref, not DerefMut, so there is no way to get &mut SelfRef, and it could not move. If another function needs a sr, we could pass my_pinned_sr to it just like handle(my_pinned_sr). handle cannot move
sr.

But what if we need mutable reference? What if we need to call push_str on sr.v? It's totally okay because it's not move v.

If we implement DerefMut to allow user to get a mutable reference directly:

impl<Ptr: DerefMut> DerefMut for MyPin<Ptr> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.ptr.deref_mut()
    }
}

User could get &mut SelfRef and move it. We lose the protection from MyPinned. User could do like this:

fn print(name: &str, pinned: &MyPin<Box<SelfRef>>) {
    println!(
        "addr of {name}.v: {:?}, value of {name}.ptr {:?}, value of {name}.v: {} , deref value of {name}.ptr: {}",
        &pinned.ptr.v as *const String,
        pinned.ptr.ptr,
        pinned.v,
        unsafe { &*pinned.ptr.ptr }
    );
}


let mut a = Box::new(SelfRef::new("hello".to_string()));
a.correct_ptr();
let mut pinned_a = MyPin::new(a);

let mut b = Box::new(SelfRef::new("world".to_string()));
b.correct_ptr();
let mut pinned_b = MyPin::new(b);

print("a", &pinned_a);
print("b", &pinned_b);
std::mem::swap(&mut *pinned_a, &mut *pinned_b); // dangerous! move by swap
print("a", &pinned_a);
print("b", &pinned_b);

It will output:

addr of a.v: 0x60000165d1e0, value of a.ptr 0x60000165d1e0, value of a.v: hello , deref value of a.ptr: hello
addr of b.v: 0x60000165d200, value of b.ptr 0x60000165d200, value of b.v: world , deref value of b.ptr: world
addr of a.v: 0x60000165d1e0, value of a.ptr 0x60000165d200, value of a.v: world , deref value of a.ptr: hello
addr of b.v: 0x60000165d200, value of b.ptr 0x60000165d1e0, value of b.v: hello , deref value of b.ptr: world

a.ptr and b.ptr both point to the wrong address.

That's the problem. We need a way to get &mut SelfRef and we need to prevent user from moving SelfRef by it. Currently, Rust compiler is not able to tell if an operation is moving T. So the official Pin chose a little bit extreme way: unsafe fn.

For T: Unpin, provide &mut by DerefMut
For T: !Unpin, provide &mut T by unsafe fn

// Only impl DerefMut for whose Target is Unpin
impl<Ptr: DerefMut<Target: Unpin>> DerefMut for MyPin<Ptr> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.ptr.deref_mut()
    }
}

impl<Ptr: DerefMut> MyPin<Ptr> {
    // as_mut is for resolving lifetime issue. Ptr has no lifetime while &mut T has
    // A bridge in MyPin<Ptr> -> MyPin<&'a mut T> -> &'a mut T
    pub fn as_mut(&mut self) -> MyPin<&mut Ptr::Target> {
        MyPin {
            ptr: &mut *self.ptr,
        }
    }
}

impl<'a, T> MyPin<&'a mut T> {
    // For T: Unpin, return &mut T directly
    pub fn get_mut(self) -> &'a mut T
    where
        T: Unpin,
    {
        self.ptr
    }

    // For T: !Unpin, return &mut T in unsafe fn to warn
    unsafe fn get_unchecked_mut(self) -> &'a mut T {
        self.ptr
    }
}

Now the previous swap will cause an error:

error[E0596]: cannot borrow data in dereference of `MyPin<Box<SelfRef>>` as mutable
   --> src/main.rs:137:20
    |
137 |     std::mem::swap(&mut *pinned_a, &mut *pinned_b);
    |                    ^^^^^^^^^^^^^^ cannot borrow as mutable
    |
    = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `MyPin<Box<SelfRef>>`

error[E0596]: cannot borrow data in dereference of `MyPin<Box<SelfRef>>` as mutable
   --> src/main.rs:137:36
    |
137 |     std::mem::swap(&mut *pinned_a, &mut *pinned_b);
    |                                    ^^^^^^^^^^^^^^ cannot borrow as mutable
    |
    = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `MyPin<Box<SelfRef>>`

The Ptr of MyPin<Box<SelfRef>> is Box<SelfRef>, whose Target is SelfRef, and SelfRef: !Unpin, so MyPin<Box<SelfRef>> does not implement DerefMut. We could not construct &mut *pinned_a and &mut *pinned_b.

If we still wants to swap, we need to write unsafe block:

unsafe {
    let a_mut = pinned_a.as_mut().get_unchecked_mut();
    let b_mut = pinned_b.as_mut().get_unchecked_mut();
    std::mem::swap(a_mut, b_mut);
}

And that's a contract between programmer and compiler: I need a &mut T, but compiler cannot prevent me from moving T when I possess &mut T. So I, as programmer, promise that I would never move T. That's the purpose of unsafe block: you're able do something dangerous in unsafe block, but you promise you would never do it.

Summary

In Rust, self-referential structs are very dangerous because of moving.
In the state machine of async/await, self-referential structs are ubiquitous, because all variables must be stored in the struct.
If you want to move T, you must have a &mut T. Some operations on &mut T will move it, while others will not.
Pin is very simple. It's just a wrapper of a pointer to T, and provide different access according to Unpin or !Unpin. If T: Unpin, then it provides full access. User could get &T and &mut T freely. Otherwise, user could only get &T. To get a &mut T, user must write unsafe block and promise that T would never move in it.

Using gRPC in React the Modern Way: From gRPC-web to Connect

Arc — Mon, 21 Apr 2025 15:55:41 +0000

Recently, I've been exploring how to use gRPC in React projects to interact with the backend. I searched for many articles online, but was surprised to find that there wasn't a single one that clearly explained it from scratch. So, I did some simple exploration and implemented a basic personnel CRUD service using React + Rust + Go.

Complete code: https://github.com/Arichy/react-rust-go-rpc. Please note that although this article introduces multiple solutions, the frontend in the code repository uses the @bufbuild + @connect suite, not grpc-web or protobuf-ts.

1. Distinguishing Concepts

Before diving into the main content, there are a few easily confused concepts that need clarification:

Feature	Protobuf	RPC	gRPC	gRPC-web	Connect
Definition	Protocol Buffers, a structured data serialization format developed by Google	Remote Procedure Call, a general concept	A high-performance RPC framework developed by Google, based on HTTP/2 and Protocol Buffers	A browser-side implementation of gRPC, allowing the frontend to directly communicate with gRPC services	A more modern RPC framework focusing on developer experience, compatible with gRPC
Creator	Google	General concept, no single creator	Google	Google	Buf company
Transport Protocol	N/A (serialization format only)	Various	HTTP/2	HTTP/1.1 or HTTP/2 (requires proxy)	HTTP/1.1 or HTTP/2
Serialization	Binary, efficient and compact	Various	Protocol Buffers	Protocol Buffers	Protocol Buffers or JSON
Browser Support	Supported via JS libraries	Not directly supported	Not directly supported	Supported via special client	Native support, no proxy needed
Code Generation	Uses compilers like protoc to generate multi-language code	Depends on implementation	Complex, requires protoc	Complex, requires protoc and plugins	Simplified, uses buf toolchain
Use Case	Efficient data exchange, cross-language systems	Distributed system communication	Microservice communication, backend services	Browser → Server communication	Full-stack applications, cross-platform
Developer Experience	Requires extra compilation steps	Basic	Feature-rich but complex configuration	Complex configuration, requires proxy	Simplified configuration, excellent DX

(The above table was generated by Github Copilot)

In summary:

Protobuf is a data format, commonly using binary serialization.
RPC is a communication concept.
gRPC is a framework that implements RPC, using Protobuf as the data format.
gRPC-web is the browser-side implementation of gRPC, but since browsers don't support HTTP/2 directly for this purpose, a proxy service is needed to convert HTTP/1.1 to HTTP/2.
Connect is a newer RPC framework, compatible with gRPC, but more modern, and also has its own Connect communication protocol.

2. Tech Stack + Structure

Frontend: React + TypeScript + Vite + gRPC related libraries (this is quite confusing, will be explained below).
gRPC Backend: Rust + tonic (a Rust implementation of gRPC).
Connect Backend: Go + connect.
Protobuf files.
envoy + Docker (Docker is optional, used because I don't want to install envoy locally).

Directory Structure (some common files omitted):

.
├── frontend/ (generated by vite, regular files omitted)
│   ├── src/
│   │   ├── gen/
│   │   └── grpc.ts
│   ├── package.json
│   ├── vite.config.ts
│   ├── buf.gen.yaml
│   └── tsconfig.json
├── rust-grpc-backend/ (a simple Rust gRPC server, regular files omitted)
│   ├── src/
│   ├── build.rs
│   └── Cargo.toml
├── go-connect-backend/ (a simple Go connect server, regular files omitted)
│   ├── gen/ (generated by `buf generate`)
│   ├── buf.yaml
│   ├── buf.gen.yaml
│   └── main.go
├── proto/
│   └── person.proto
├── envoy.yaml
└── docker-compose.yml

envoy

First, you need to know that gRPC is based on HTTP/2. Although modern browsers support HTTP/2, JavaScript's fetch API cannot directly control the underlying capabilities of HTTP/2 like streams and header frames. This prevents gRPC from being used natively in the browser. For example, gRPC has specific frame format requirements for HTTP/2, but the fetch API doesn't provide such capabilities. Therefore, we need a proxy service to convert the HTTP/1.1 requests sent by the browser into HTTP/2 requests. Currently, a popular proxy service is envoy (don't worry, only basic usage is needed, it's okay if you don't understand this).

Create an envoy.yaml file in the root directory with the following content:

admin:
  access_log_path: /tmp/admin_access.log
  address:
    socket_address: { address: 0.0.0.0, port_value: 9901 }

static_resources:
  listeners:
    - name: listener_0
      address:
        socket_address: { address: 0.0.0.0, port_value: 8080 } # Address where frontend requests are sent
      filter_chains:
        - filters:
            - name: envoy.filters.network.http_connection_manager
              typed_config:
                '@type': type.googleapis.com/envoy.extensions.filters.network.http_connection_manager.v3.HttpConnectionManager
                codec_type: auto
                stat_prefix: ingress_http
                route_config:
                  name: local_route
                  virtual_hosts:
                    - name: local_service
                      domains: ['*']
                      routes:
                        - match: { prefix: '/' }
                          route:
                            cluster: person_service
                            timeout: 0s
                            max_stream_duration:
                              grpc_timeout_header_max: 0s
                      cors:
                        allow_origin_string_match:
                          - prefix: '*'
                        allow_methods: GET, PUT, DELETE, POST, OPTIONS
                        allow_headers: keep-alive,user-agent,cache-control,content-type,content-transfer-encoding,x-accept-content-transfer-encoding,x-accept-response-streaming,x-user-agent,x-grpc-web,grpc-timeout
                        max_age: '1728000'
                        expose_headers: grpc-status,grpc-message
                http_filters:
                  - name: envoy.filters.http.grpc_web
                    typed_config:
                      '@type': type.googleapis.com/envoy.extensions.filters.http.grpc_web.v3.GrpcWeb
                  - name: envoy.filters.http.cors
                    typed_config:
                      '@type': type.googleapis.com/envoy.extensions.filters.http.cors.v3.Cors
                  - name: envoy.filters.http.router
                    typed_config:
                      '@type': type.googleapis.com/envoy.extensions.filters.http.router.v3.Router
  clusters:
    - name: person_service
      connect_timeout: 0.25s
      type: logical_dns
      http2_protocol_options: {}
      lb_policy: round_robin
      load_assignment:
        cluster_name: person_service
        endpoints:
          - lb_endpoints:
              - endpoint:
                  address:
                    socket_address:
                      # address: backend # Use this if running backend + envoy with docker-compose
                      address: host.docker.internal # Use this if only running envoy with Docker
                      port_value: 50051 # backend's grpc server port

It's okay if you don't understand it; I don't either. This isn't the main point; just pay attention to the two ports and one address commented above. Once created, you can run it using docker-compose. Below is a simple docker-compose.yml file:

services:
  # Envoy proxy for gRPC-Web support
  envoy:
    image: envoyproxy/envoy:v1.33-latest
    ports:
      - '8080:8080'
    volumes:
      - ./envoy.yaml:/etc/envoy/envoy.yaml # Mount envoy.yaml into the container

Now you can run envoy using docker-compose up. This command will run envoy and map port 8080 to the host machine's port 8080, waiting to forward gRPC-web requests from the frontend to the Rust gRPC server on port 50051.

3. Handling Proto Files + gRPC Communication

Here we use proto/person.proto as an example, defining basic CRUD operations (this file was written for me by Copilot; it returns a paginated result when Listing People, but the pagination logic isn't implemented, just to demonstrate proto file definition):

syntax = "proto3";

package person;

// The Person message represents an individual person in our system
message Person {
  string id = 1;
  string name = 2;
  string email = 3;
  int32 age = 4;
}

// Request message for creating a new person
message CreatePersonRequest {
  Person person = 1;
}

// Response message for creating a new person
message CreatePersonResponse {
  Person person = 1;
}

// Request message for retrieving a person by ID
message GetPersonRequest {
  string id = 1;
}

// Response message for getting a person
message GetPersonResponse {
  Person person = 1;
}

// Request message for updating a person
message UpdatePersonRequest {
  Person person = 1;
}

// Response message for updating a person
message UpdatePersonResponse {
  Person person = 1;
}

// Request message for deleting a person
message DeletePersonRequest {
  string id = 1;
}

// Response message for deleting a person
message DeletePersonResponse {
  bool success = 1;
}

// Request message for listing people
message ListPeopleRequest {
  // Optional pagination fields
  int32 page_size = 1;
  int32 page_token = 2;
}

// Response message for listing people
message ListPeopleResponse {
  repeated Person people = 1;
  int32 next_page_token = 2;
}

// The PersonService provides CRUD operations for managing people
service PersonService {
  // Create a new person
  rpc CreatePerson (CreatePersonRequest) returns (CreatePersonResponse);

  // Get a person by ID
  rpc GetPerson (GetPersonRequest) returns (GetPersonResponse);

  // Update an existing person
  rpc UpdatePerson (UpdatePersonRequest) returns (UpdatePersonResponse);

  // Delete a person by ID
  rpc DeletePerson (DeletePersonRequest) returns (DeletePersonResponse);

  // List all people with optional pagination
  rpc ListPeople (ListPeopleRequest) returns (ListPeopleResponse);
}

3.1 Rust Side

On the Rust side, we need to use tonic to generate gRPC-related code. This part is not the focus and is quite simple, so I won't elaborate; you can check the documentation yourself. Essentially, you write a build.rs file, and tonic-build will automatically compile the proto file into Rust code, which we can then use in our Rust code.

3.2 Frontend

This part is the main focus of this article and the most troublesome. When I was looking through the documentation, I got confused by a bunch of libraries and spent a long time figuring out what each library does. This is mainly because gRPC JS can be used not only in the browser but also in Node.js, so many libraries are targeted at Node.js, but we need the browser-side ones. Therefore, you need to install many libraries; some are purely for the JS language itself, platform-independent, while others provide browser support.

Official Implementation

TL;DR: Using the official implementation is not recommended. The libraries are confusing, the build command is disgusting, and it only supports CommonJS, not ES modules.

The official gRPC-web implementation is grpc-web. You first need to install a compiler:

brew install protobuf

This command installs protobuf, used via protoc in the command line. It's a compiler we need to compile proto files into code for other languages. However, since protobuf officially only supports C++, C#, Dart, Go, Java, Kotlin, Python, and not JS, we need to install a plugin to generate JS code. This plugin is protoc-gen-js, which can be installed via npm. The official documentation tutorial suggests global installation, but I personally prefer local installation within the project.

A project using the official implementation should have the following libraries in its package.json:

{
  "dependencies": {
    "grpc-web": "Provides the ability for the browser to communicate with the gRPC server, focusing on communication capability",
    "google-protobuf": "Provides the JavaScript implementation of protobuf, focusing on protobuf serialization and deserialization capabilities"
  },
  "devDependencies": {
    "protoc-gen-js": "The plugin mentioned above, invoked by protoc, used to compile proto files into JS code, focusing on compilation capability",
    "protoc-gen-grpc-web": "Another plugin, invoked by protoc, generates grpc-web related client code"
  }
}

Then run a script to compile the proto file into JS code:

{
  "scripts": {
    "gen-proto": "rm -rf src/generated && mkdir -p src/generated && protoc -I=../proto --js_out=import_style=commonjs,binary:src/generated --grpc-web_out=import_style=commonjs,mode=grpcwebtext:src/generated ../proto/*.proto"
  }
}

Honestly, just seeing this compilation command makes my eyes glaze over. I'll try to explain what it does. Ignoring the first two parts that delete the existing directory and create a new one, let's look at the protoc command:

-I=../proto: indicates where to find the proto files. Since this package.json is in the frontend directory, it's the parent directory ../proto.
--js_out=import_style=commonjs,binary:src/generated: the js_out is passed to the protoc-gen-js plugin, explained in detail below.
../proto/\*.proto are the proto files to be compiled, also direct parameters passed to protoc.

The format of --js_out looks overly complicated: --js_out=[OPTIONS:]output_dir, where OPTIONS are comma-separated options, and output_dir is the output directory. Here, OPTIONS has two options:

import_style=commonjs specifies that the generated JS code uses CommonJS modules. This option is optional; if not specified, the default is commonjs.
binary indicates that the generated JS code should support binary serialization and deserialization of messages.

src/generated is the path for the generated JS code.

Then there's the --grpc-web_out parameter, which has the same format as --js_out, so I won't repeat the details.

Running this command will generate two files under src/generated:

person_pb.js: This file contains JS code generated by protoc-gen-js, including message types defined in the proto file and serialization/deserialization logic.
person_grpc_web_pb.js: This file contains JS code generated by protoc-gen-grpc-web, including the gRPC client code, which is what we need to call to send requests.

Unfortunately, the JS code generated by protoc-gen-js only supports CommonJS, not ESM, and uses the exports variable.

goog.object.extend(exports, proto.person);

I couldn't find a way to successfully bundle the generated code with Vite, so I don't recommend using the official implementation.

protobuf-ts

protobuf-ts is a third-party implementation. This solution only requires installing two libraries:

{
  "dependencies": {
    "@protobuf-ts/grpcweb-transport": "gRPC runtime library"
  },
  "devDependencies": {
    "@protobuf-ts/plugin": "protoc compiler plugin, used to compile proto files into TS code"
  }
}

Then modify the compilation command:

{
  "scripts": {
    "gen-proto": "rm -rf src/generated && mkdir -p src/generated && protoc -I=../proto --ts_out=src/generated ../proto/*.proto"
  }
}

As you can see, this solution still relies on the protoc command, but doesn't require installing the protoc-gen-js and protoc-gen-grpc-web plugins. You only need to install the @protobuf-ts/plugin plugin, and the command is much simpler. This plugin is called by protoc to compile proto files into TS code. The advantage of this solution is that the generated TS code uses ESM modules and can be used directly in Vite.

Then update frontend/src/grpc.ts:

import { GrpcWebFetchTransport } from '@protobuf-ts/grpcweb-transport';
import { PersonServiceClient } from './generated/person.client';

const apiUrl = 'http://localhost:8080';

const transport = new GrpcWebFetchTransport({
  baseUrl: apiUrl,
});
export const personClient = new PersonServiceClient(transport);

Now you can happily use it in React (here integrated with react-query):

import { personClient } from './grpc';

// in component
const peopleQueryKey = ['people'];

// READ
const { data: people } = useQuery({
  queryKey: peopleQueryKey,
  queryFn: async () => {
    const response = await personClient.listPeople({ pageSize: 1, pageToken: 1 });
    return response.response.people;
  },
});

// CREATE
const handleAddPerson = async (person: Person) => {
  try {
    await personClient.createPerson(CreatePersonRequest.create({ person })); // option 1: using create method
    queryClient.invalidateQueries({ queryKey: peopleQueryKey });
    setSelectedPerson(null);
  } catch (err) {
    console.error('Error adding person:', err);
  }
};

// UPDATE
const handleUpdatePerson = async (person: Person) => {
  try {
    await personClient.updatePerson({ person }); // option 2: directly pass params
    queryClient.invalidateQueries({ queryKey: peopleQueryKey });

    setSelectedPerson(null);
  } catch (err) {
    console.error('Error updating person:', err);
  }
};

Next, run everything one by one:

docker-compose up to run envoy.
Enter rust-grpc-backend, run cargo run to start the Rust gRPC server.
Enter frontend, run yarn dev to start the frontend. 4. Open your browser and visit http://localhost:5173 (Vite's default port).

bufbuild + connect Solution

This is another more systematic and modern third-party solution, requiring the installation of the following libraries:

{
  "dependencies": {
    "@bufbuild/protobuf": "Core library for protobuf, provides runtime support",
    "@connectrpc/connect": "Core library for connect, provides platform-independent connect runtime support",
    "@connectrpc/connect-web": "Connect's gRPC-web plugin, used to provide gRPC-web communication capability in the frontend",
    "@connectrpc/connect-query": "Optional, provides react-query support, although you can use react-query without installing this"
  },
  "devDependencies": {
    "@bufbuild/buf": "Proto file compiler",
    "@bufbuild/protoc-gen-es": "Compiler plugin, generates ES code"
  }
}

The reason for having two namespaces, bufbuild and connect, is that they serve different purposes. @bufbuild libraries handle proto files and the protobuf format, while @connect libraries handle the connect/gRPC protocol.

Using this solution frees you from the complex protoc command, replacing it with the buf command. This command requires creating a buf.yaml file in the frontend directory with the following content:

version: v2 # migration from v1 guide: https://github.com/connectrpc/connect-es/blob/main/MIGRATING.md
inputs:
  - directory: ../proto

clean: true
plugins:
  - local: protoc-gen-es # This plugin is called by buf, used to compile proto files into TS code
    opt: target=ts # Indicates we want to generate TS code
    out: src/gen # Directory where generated code is stored
    include_imports: true

Then add a command in package.json:

{
  "scripts": {
    "gen-proto": "buf generate"
  }
}

Running this command will generate a file under src/gen: src/gen/person_pb.ts. Then update the frontend/src/grpc.ts file:

import { createClient, Transport } from '@connectrpc/connect';
import { createGrpcWebTransport } from '@connectrpc/connect-web';

import { PersonService } from './gen/person_pb'; // Adjusted import path based on buf.gen.yaml

const apiUrl = 'http://localhost:8080'; // Envoy proxy address

// Use gRPC-web transport as the Rust backend uses gRPC
export const transport: Transport = createGrpcWebTransport({
  baseUrl: apiUrl,
});

// Create the client using the generated service definition and the transport
export const personClient = createClient(PersonService, transport);

The @connectrpc/connect-web library also has a method createConnectTransport, which creates a transport that uses the Connect protocol to communicate with the backend instead of the gRPC-web protocol. However, this requires the backend to use a Connect implementation, not a gRPC implementation. Currently, Connect officially supports Go, Node.js, Swift, Kotlin, Dart, but not yet Rust. So here, we can only use the gRPC-web protocol. But Connect implementations are generally more modern than gRPC implementations, so if the backend supports Connect, consider using the `createConnectTransport

4. Go connect server

As mentioned at the beginning of the article, Connect is a newer RPC framework, compatible with gRPC, but more modern, and also has its own Connect communication protocol. Let's explore how to implement a Connect server using Go. Here we use connect-go. After installing the necessary tools according to the tutorial, create a new Go project directory named go-connect-server in the project root, and execute the following inside it:

Step 1: go mod init example.com/go-connect-server Initialize the Go project with the package name example.com/go-connect-server.

Step 2: buf config init, which will generate a buf.yaml file; you can ignore its contents.

Step 3: Create a buf.gen.yaml file with the following content: (there is something wrong with the markdown)

version: v2
inputs:

directory: ../proto

clean: true
plugins:

local: protoc-gen-go # Compiles proto files into Go code out: gen opt: paths=source_relative

local: protoc-gen-connect-go # Generates Connect protocol >related code out: gen opt: paths=source_relative `

Step 4: Very importantly, modify the person.proto file by adding the following line

option go_package = "example.com/go-connect-backend/gen;person";

go_package defines the package name where the generated Go code for this proto file resides. example.com/go-connect-backend is the Go project's module path, gen is the directory where the generated Go code files are located, and person is the package name.

Step 5: Execute buf generate. This will generate a person.pb.go file in the go-connect-backend/gen directory, containing the Go code compiled from the proto file, including message types and serialization/deserialization logic. It will also generate a person.connect.go file in the go-connect-backend/gen/personconnect directory, which handles Connect protocol communication.

Then, follow the tutorial to write a basic service, paying attention to potentially handling CORS. After the service starts, the frontend can use the createConnectTransport method to communicate with the backend using the Connect protocol. Connect uses HTTP/1.1 (though it also supports HTTP/2) + JSON (or Protobuf) as the transport protocol, and works in the browser without needing an additional proxy service, allowing the frontend to directly request the backend.

5. Summary

This article introduced how to use gRPC in a React project to interact with a backend gRPC server, using envoy as a proxy, and also briefly explored a Go Connect server. Here are some key takeaways:

Distinguish between Protobuf and gRPC. The former is a data format, the latter a communication protocol, which is why you need to install a bunch of packages, as different packages handle different parts.
gRPC is based on HTTP/2, but browser JS lacks the ability to control the underlying capabilities of HTTP/2, so a proxy service is needed to convert HTTP/1.1 to HTTP/2. Envoy is a popular choice.
The official grpc-web implementation is relatively old. It's recommended to use popular third-party solutions like protobuf-ts or Connect.
Connect is a newer RPC framework, compatible with gRPC, but more modern, and also has its own Connect communication protocol. If the backend has a Connect implementation, consider using the createConnectTransport method, which eliminates the need for a proxy service like envoy; you can directly request the service.

6. Fun facts

I personally have a strong aversion to cluttering my hard drive and dislike leaving files scattered across the filesystem, which eventually fills up the disk. Therefore, I minimize global command installations as much as possible, which is why I use Docker to run envoy instead of installing and running envoy globally.
In the frontend, we installed @bufbuild/buf and @bufbuild/protoc-gen-es. These libraries are installed into node_modules and run via npm scripts. Some tutorials might suggest global installation; you can decide based on personal preference.
Since Go doesn't have a mechanism like npm scripts, several Go tools have to be installed globally using go install. Here, we installed grpcurl, buf, protoc-gen-go, and protoc-gen-connect-go. If you've already installed grpcurl via brew, you don't need to install it again with Go. We installed buf globally here; actually, the @bufbuild/buf installed in the frontend is a wrapper around this buf. @bufbuild/buf fetches the buf binary into node_modules and then calls it itself.

Variance - best perspective of understanding lifetime in Rust

Arc — Sat, 19 Oct 2024 10:33:59 +0000

This article will explain variance and lifetime in Rust, with a combination with TypeScript. It's suit for Rust beginners with TypeScript background.

What is variance

Variance is a common concept in type system in programming languages and wildly exists in many programming languages. Variance is used to describe the feasibility of placing an A at a place which requires a B, if type A and type B have a parent-child relationship.

If B is subtype of A, we could say B is more useful (or at least as useful as) than A, because B has all features which A has. Basically, along the dataflow direction, we could place a B at a place where an A is required. Variance is a conclusion for these scenarios, hiding the detail of dataflow direction.

Variance includes:

covariance
invariance
contravariance

The general description of variance is:
T is covariant / invariant / contravariant over U. T is the main type to focus on, while U is part of T. Like in TypeScript:

T is covariant over T
T[] is covariant over T
(item: T) => void is contravariant over T It's very important. It clarifies that variance is the relationship between a type and an inner type of it.

In Rust, there is no inheritance, so most of types have no parent-child relationship with each other. For better understanding, I'll use TypeScript to explain, with strict: true in tsconfig.json. I'll focus on explaining covariance and invariance, as these two are crucial for understanding lifetimes. Finally, I will briefly introduce contravariance.

Covariance

Covariance means you could place a Child at a place requiring a Parent.

class Animal {
  name = '';

  hello() {}
}

class Cat extends Animal {
  catchJerry() {}
}

function say(animal: Animal) {
  person.hello();
}

let cat = new Cat();

say(cat);

say expects the person to be Animal, but we could pass a Cat when calling it. Because Cat is subtype of Animal, Cat has all properties and methods in Animal. In other word, Cat is more useful than Animal. So Animal is covariant over Animal.

Invariance

invariance means you could neither place a Child at a Parent place, nor could you place a Parent at a Child place. If a place needs Child, you could only place a Child exactly.

I didn't find invariance example in TypeScript, so I'll use a piece of code which could pass the TS compiler even if strict: true is enabled, but it will run into runtime error.

const cat = new Cat('Tom');
const cats: Cat[] = [cat];

function handle(animals: Animal[]) {
    cats.push(new Animal('animal'));
}

handle(cats);

cats.forEach(cat => {
    cat.catchJerry(); // oops!
});

We passed a cats: Cat[] to handle, while handle expects it to be Animal[], so it's absolute legal to insert a new Animal into it. However, cats does not know there is an Animal inside it. It still regards all the elements as Cat, resulting in the error.

On the other hand, if handle expects the argument to be Cat[], obviously we could not pass an Animal[]. We could only pass a type T[] if the place needs a T[]. This is called invariance, only the exactly same type is allowed.

To emphasize again, this example code is only meant to illustrate a case that T[] is invariant in T. In reality, TS does not handle it this way. In TS, T[] is covariant in T.

Data Flow Direction

Now let's break it down to see the difference. Why is it that sometimes you can pass a subtype in a place that requires a certain type, but other times you cannot? The reason is about read and write. In read-only scenarios, you can pass a subtype. In write-only scenarios, you can pass a supertype. In read-write scenarios, only the original type can be passed.

TypeScript does not support pass-by-reference, so I'll use a pice of pseudo code to illustrate.

let animal: Animal = some_animal;
let cat:Cat = some_cat;

// readonly
let need_an_animal: Animal = some_cat; // place Child at Parent
need_an_animal.hello();

// writeonly
let need_a_cat: &Cat = &some_animal; // place Parent at Child
*need_a_cat = another_cat; // now `some_animal` is pointing to a cat, it's ok
some_animal.hello();

The fundamental reason for variance is that the data flow direction of read and write operations is opposite. Let's call the needed value (argument) is need, while the real value is real. Under read operations, data is flowing from real to need, so real needs to contain all info in need, or let's say real should be at least as useful as need. Conversely, under read operations, data is flowing from need to real, so need needs to contain all info in real, or let's say need should be at least as useful as real.

Mutability and Write

The reason why TS allows the erroneous code above, is that TS has no mutability declaration. TS does not know what would handle do on animals. Readonly? Or write? If TS was very strict and assumed both read and write operations would be done, the argument would only be exactly Animal[], which would lose much flexibility. So TS strikes a balance between strictness and flexibility and allows the code.

On the contrary, it's required to declare mutability in Rust, so the code above could not be compiled in Rust. That's the reason for many lifetime related errors as well.

A simple summary:

In TS, T is covariant in T, because TS thinks read is more fundamental than write, and it will protect read first.
In Rust, &T is covariant in T, because you could not mutate T via &T. Rust will guarantee that it's read-only and it's safe to read.
In Rust, &mut T is invariant, because you could mutate T via &mut T.

Then let's talk about lifetime.

Variance in lifetime

There is no inheritance in Rust, so many types have no a parent-child relationship between each other. However, lifetimes do have. If 'a encloses 'b , then 'a is subtype of 'b ('a: 'b ). So lifetimes and variance are naturally tied together.
Rust official reference lists some variance

Type	Variance in `'a`	Variance in `T`
`&'a T`	covariant	covariant
`&'a mut T`	covariant	invariant
`*const T`		covariant
`*mut T`		invariant
`[T]` and `[T; n]`		covariant
`fn() -> T`		covariant
`fn(T) -> ()`		contravariant
`std::cell::UnsafeCell<T>`		invariant
`std::marker::PhantomData<T>`		covariant
`dyn Trait<T> + 'a`	covariant	invariant

Let's focus on the first 2 rows. Please pay special attention, &'a T is one type, but it contains other 2 types: &'a and T. &'a T has different variance in &'a and 'T. Refer to the table, we could see both &'a T and &'a mut T are covariant in 'a. That's to say, we could place a &'b T / &'b mut T at a place requiring a &'a T / &'a mut T, as long as 'b: 'a . Please remember this, and it will make the lifetime of every reference much clearer.

Covariance Lifetime

You must have seen the code below for many times:

fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

fn main() {
    let string1 = "hello".to_string(); // 1
    let string1_ref = &string1; // 2

    let res: &str; // 3

    { // 4
        let string2 = "myworld".to_string(); // 5
        res = longest(string1_ref, &string2); // 6
    } // 7

    println!("{}", res); // 8
    println!("{}", string1_ref); // 9
}

Now, forget about "'a is the shorter one of x and y". Let's understand it via variance. 'a will be a specific type, instead of a "shorter one". I think a specific type is easier to understand than "shorter one", "at least", "at most".

For convenience, I'll use 1~2 to represent the lifetime between position 1 and 2 in code.

The code above is erroneous obviously, because the return value used at 8 could reference to string2, while string2 is dropped at 7. Form the perspective of generic, longest function has a lifetime generic 'a , takes an x with 'a, a y with 'a, and return a value with 'a. So Rust will start generic inference based on the context:

string1_ref has a lifetime 2~9, and it could extend to 1~10
&string2 has a lifetime 6~6, and it could extend to 6~7
res is expected to have a lifetime 6~8 (Not starts from 3 because res at 3 is not read. The read of res at 8 is reading the value set at 6).

The inference process is:

Set 'a to 6~8, because the return value requires the lifetime to be at least 6~8. Now, longest takes two params with lifetime 3~8, and return a value with 6~8.
Then check the first actual param string1_ref. It's expected to have a lifetime 6~8, and it's actual lifetime is 2~9. 2~9 is subtype of 6~8. According to covariance, it's legal.
Then check the second actual param &string2. It's expected to have a lifetime 6~8, but it's actual lifetime is 6~6. Rust tries to extend its lifetime, but could only reach 6~7. 6~7 is not subtype of 6~8, but supertype. So it's illegal, and Rust throws an error:

error[E0597]: `string2` does not live long enough
  --> src/bin/lifetime.rs:17:36
   |
16 |         let string2 = "myworld".to_string(); // 5
   |             ------- binding `string2` declared here
17 |         res = longest(string1_ref, &string2); // 6
   |                                    ^^^^^^^^ borrowed value does not live long enough
18 |     } // 7
   |     - `string2` dropped here while still borrowed
19 |
20 |     println!("{}", res); // 8
   |                    --- borrow later used here

Now the error message makes lot's of sense. &string2 is expected to have a lifetime at least as long as 6~8, but the max lifetime of it is 6~7. That's why &string2 does not live long enough.

Let's go through the correct code with the similar process:

fn main() {
    let string1 = "hello".to_string(); // 1
    let string1_ref = &string1; // 2

    let res: &str; // 3

    { // 4
        let string2 = "myworld".to_string(); // 5
        res = longest(string1_ref, &string2); // 6
        println!("{}", res); // 7
    } // 8

    println!("{}", string1_ref); // 9
} // 10

'a is set to 6~7.
Check the first actual param string1_ref. It has a lifetime 2~9, and could be assigned to 6~7.
Check the second actual param &string2. It has a lifetime 6~6, so Rust tries to extend it to 6~7, successfully.

Please attention that now the lifetime of &string2 extends to 6~7, and it's simple to prove it. Rust does not allow any overlap between an immutable reference and a mutable reference to the same value. Let's add a new line above position 7:

let mut string2 = "myworld".to_string(); // 5, make it mut
res = longest(string1_ref, &string2); // 6
println!("{}", &mut string2); // add a mutable reference
println!("{}", res); // 7

An error arises:

17 |         res = longest(string1_ref, &string2); // 6
   |                                    -------- immutable borrow occurs here
18 |         println!("{}",&mut string2);
   |                       ^^^^^^^^^^^^ mutable borrow occurs here
19 |         println!("{}", res); // 7
   |                        --- immutable borrow later used here

It's clear that the lifetime of &string2 is actually extended to position 7, so we cannot use &mut string2 between position 6 and 7.

Invariance Lifetime

Let's recall the variance table: &'a T is covariant in T, but &'a mut T is invariant in T. Let's show it:

fn test<'a>(vec: &'a Vec<&'a i32>) {
    todo!()
}

static GLOBAL_1: i32 = 1;
static GLOBAL_2: i32 = 2;
static GLOBAL_3: i32 = 3;

fn main() {
    let vec: Vec<&'static i32> = vec![&GLOBAL_1, &GLOBAL_2, &GLOBAL_3]; // 1
    test(&vec);
    println!("{:?}", vec);
    // 2
}

test accepts an immutable reference with lifetime 'a to a vector, and the element in the vector should have the same lifetime 'a. In main, we created a Vec<&'static i32>, then pass an immutable reference of it to test.

Let's clarify the inference context:

formal param: &'a  Vec<&'a      i32>
actual param: &2~2 Vec<&'static i32>

Generic inference always prefers the parent type, so 'a will be inferred to 2~2, instead of 'static. Then, the inner 'static is assigned to 2~2 by covariance. Compile successfully.

Then let's take a look at mut:

fn test<'a>(vec: &'a mut Vec<&'a i32>) {
    todo!()
}

static GLOBAL_1: i32 = 1;
static GLOBAL_2: i32 = 2;
static GLOBAL_3: i32 = 3;

fn main() {
    let mut vec: Vec<&'static i32> = vec![&GLOBAL_1, &GLOBAL_2, &GLOBAL_3]; // 1
    test(&mut vec); // 2
    println!("{:?}", vec); // 3
} // 4

Similarly, let's clarify the inference context:

formal param: &'a  mut Vec<&'a      i32>
actual param: &2~2 mut Vec<&'static i32>

&'a mut T is invariant in T, so T must be the certain type of what it is in actual param. T is Vec<&'static i32>, so 'a is inferred to 'static. Unfortunately, &mut vec at position 2 is never 'static, leading to compilation error:

error[E0597]: `vec` does not live long enough
  --> src/bin/lifetime.rs:11:10
   |
10 |     let mut vec: Vec<&'static i32> = vec![&GLOBAL_1, &GLOBAL_2, &GLOBAL_3]; // 1
   |         -------  ----------------- type annotation requires that `vec` is borrowed for `'static`
   |         |
   |         binding `vec` declared here
11 |     test(&mut vec); // 2
   |          ^^^^^^^^ borrowed value does not live long enough
12 |     println!("{:?}", vec);
13 | }
   | - `vec` dropped here while still borrowed

error[E0502]: cannot borrow `vec` as immutable because it is also borrowed as mutable
  --> src/bin/lifetime.rs:12:22
   |
10 |     let mut vec: Vec<&'static i32> = vec![&GLOBAL_1, &GLOBAL_2, &GLOBAL_3]; // 1
   |                  ----------------- type annotation requires that `vec` is borrowed for `'static`
11 |     test(&mut vec); // 2
   |          -------- mutable borrow occurs here
12 |     println!("{:?}", vec);
   |                      ^^^ immutable borrow occurs here

Rust has inferred and marked 'a as 'static successfully. We could tell from the error message:

type annotation requires that `vec` is borrowed for `'static`

The inference results in the two errors:

vec does not live long enough as 'static. It's dropped at position 4.
Since the &mut vec is static, it could last forever, so any other reference to vec is not allowed.

A more complex example

struct Interface<'a> {
    manager: &'a mut Manager<'a>,
}

impl<'a> Interface<'a> {
    pub fn noop(self) {
        println!("interface consumed");
    }
}

struct Manager<'a> {
    text: &'a str,
}

struct List<'a> {
    manager: Manager<'a>,
}

impl<'a> List<'a> {
    pub fn get_interface(&'a mut self) -> Interface<'a> {
        Interface {
            manager: &mut self.manager,
        }
    }
}

fn main() {
    let mut list = List { // 1
        manager: Manager { text: "hello" },
    };

    list.get_interface().noop(); // 2

    println!("Interface should be dropped here and the borrow released"); // 3

    // this fails because inmutable/mutable borrow
    // but Interface should be already dropped here and the borrow released
    use_list(&list); // 4
}

fn use_list(list: &List) {
    println!("{}", list.manager.text);
}

The code will throw an error at position 4:

error[E0502]: cannot borrow `list` as immutable because it is also borrowed as mutable
  --> src/bin/lifetime.rs:39:14
   |
33 |     list.get_interface().noop(); // 2
   |     ---- mutable borrow occurs here
...
39 |     use_list(&list); // 4
   |              ^^^^^
   |              |
   |              immutable borrow occurs here
   |              mutable borrow later used here

Let's try figuring out the reason and fixing it from the perspective of variance.

At position 2, list.get_interface().noop() will create an implicit &'b mut list<'a> automatically, because list.get_interface() will be desugared to List::get_interface(&mut list).
list contains a lifetime 'a. Please attention, list contains lifetime 'a, instead of having lifetime 'a. Obviously 'a is 1~4, since list is used at position 1 and 4.
Take a look at the signature of get_interface: for a list which contains lifetime 'a, the param is &'a mut self, which is actually &'a mut list<'a>.

Check the inference context:

formal param: &'a mut list<'a>
actual param: &'b mut list<1~4>

Since &'a mut list<'a> is invariant in list<'a>, 'a will be assigned the value of 1~4, and the implicit reference lifetime 'b will be assigned the value of 1~4 as well (actually 'b could be bigger than 1~4 due to covariance) Now, at position 4, there are both a mutable reference &1~4 mut list<1~4>, and an immutable reference &list, causing error.

Let try fixing it.

Method 1

Although &'a mut T is invariant in T, &'a T is covariant in T. So what we need to do is just remove all mut and turn it into covariant, preventing the first 'a from being assigned as the 'a in T directly.

struct Interface<'a> {
    manager: &'a Manager<'a>,
}

impl<'a> Interface<'a> {
    pub fn noop(self) {
        println!("interface consumed");
    }
}

struct Manager<'a> {
    text: &'a str,
}

struct List<'a> {
    manager: Manager<'a>,
}

impl<'a> List<'a> {
    pub fn get_interface(&'a self) -> Interface<'a> {
        Interface {
            manager: &self.manager,
        }
    }
}

fn main() {
    let mut list = List { // 1
        manager: Manager { text: "hello" },
    };

    list.get_interface().noop(); // 2

    println!("Interface should be dropped here and the borrow released"); // 3

    // this fails because inmutable/mutable borrow
    // but Interface should be already dropped here and the borrow released
    use_list(&mut list); // 4
}

fn use_list(list: &mut List) {
    println!("{}", list.manager.text);
}

Now, 'a will be inferred to 2~2. For the implicit &'b mut list<'a> at position 2, the 'b is 1~4, which could be assigned to 'a by covariance. Furthermore, we replace &list with &mut list at position 4 without error, proving that the implicit &list created at position 2 does not really live at position 4.

Method 2

In method 1, we removed mut, resulting in the immutability of Interface. Now let's see how to keep mut.

The root cause is that &'a mut list<'a> is invariant in list<'a> and the second 'a will be inferred to 1~4, forcing the first 'a to be at least 1~4. However, it's not necessary to connect the two lifetime. So we could decouple them by introducing a new generic lifetime 'b. The expected inference result is 'a is 1~4 while 'b is 2~2 so that 'b will not affect the further references to list<'a>.

    pub fn get_interface<'b>(&'b mut self) -> Interface<'a>

But there is another error:

   |
19 |   impl<'a> List<'a> {
   |        -- lifetime `'a` defined here
20 |       pub fn get_interface<'b>(&'b mut self) -> Interface<'a> {
   |                            -- lifetime `'b` defined here
21 | /         Interface {
22 | |             manager: &mut self.manager,
23 | |         }
   | |_________^ method was supposed to return data with lifetime `'a` but it is returning data with lifetime `'b`

It's because now the lifetime is like (pseudo code):

    pub fn get_interface<'b>(self: &'b mut List<'a>) -> Interface<'a> {
        Interface {
            manager: &'b mut self.manager<'a>,
        }
    }

Please pay special attention, the lifetime contains in self.manager is different from the lifetime of self.manager. The former one is actually lifetime of the &str behind self.manager.text, while the latter one is of self.manager. The 'b created in the function body in &'b mut self.manager<'a> is from the param self: &'b mut List<'a>.

The compiler tells us to add 'b: 'a, because the expected result.manager needs to be &'a mut self.manager<'a> while the actual value is &'b mut self.manager<'a>. According to covariance, 'b must outlive 'a. But we could add it, since it will extend the lifetime of the implicit &mut list and cause the same error as original version.
We need to decouple the lifetime at root: Interface<'a>. It should have two lifetime generics.

struct Interface<'b, 'a> {
    manager: &'b mut Manager<'a>,
}

impl<'b, 'a> Interface<'b, 'a> {
    pub fn noop(self) {
        println!("interface consumed");
    }
}

    pub fn get_interface<'b>(&'b mut self) -> Interface<'b, 'a>

Compiled successfully. Now 'b is 2~2, while 'a is 1~4. Perfect!

Contravariance

Lastly, let's have a look at contravariance quickly. It's mainly used in function types.

In TypeScript, T is covariant in T, but (param: T) is contravariant in T.

function handleFn(callback: (items: Cat[]) => void) {
  callback([new Cat('Tom')]);
}

handleFn((items: Animal[]) => {
  items.push(new Animal('Tom'));
});

The param of handleFn is a callback function: (items: Cat[]) => void, but we could pass (items: Animal[]) => void indeed. Because when handleFn is called, an items will be passed. The data flow is from handleFn to callback. callback will read the items by formal param. callback must assume it as a base type instead of a super type.

But not the other way around. If callback expects (items: Animal[]) => void but it gets (items: Cat[]) => void, the handleFn may pass Animal[] and callback reads it as Cat[], causing error.

Summary

We've talked about variance and how to understand lifetime from the view of variance. Here are some key takeaways:

&'a T is covariant in both 'a and T, which means that a subtype of 'a (which is larger than 'a) could be substituted for 'a, and a subtype of T could be substituted for T.
&'a mut T is covariant in 'a, but invariant in T. So if there is some lifetime 'whatever in T, the 'whatever will be inferred to the lifetime of the actual value.

Tips

Generally speaking, never write code like

impl<'a> SomeStruct<'a> {
    fn some_method(&'a mut self) {}
}

Once some_struct.some_method is called, the lifetime 'a of the implicit mutable reference &'a mut self will be tied with lifetime in self, and it's not allowed to use some_struct anymore. Because if it's used later, the lifetime in it will extend at the later position, causing the coexistence of mutable reference and any other reference in the later position.

A common TypeScript error with useRef

Arc — Mon, 15 Apr 2024 15:37:09 +0000

All scenarios in this article are under tsconfig.compilerOptions: strict: true or strictNullChecks: true.

Problem

As is known to us, useRef is to create a ref object which will persist for the full lifetime of the component in React. One of the most significant uses is to manipulate DOMs:



function App() {
    const domRef = useRef<HTMLDivElement>(null);

    useEffect(()=>{
        if (domRef.current) {
            domRef.current.innerText = 'hello world';
        }
    }, []);

    return <div ref={domRef}></div>
}

And it's used to hook an object which doesn't affect the render progress of React into the component as well. For instance, if there is a store object and you want to use it in the component, you might write code like this:



class Store {
    get() {}
    set() {}
}

function App() {
    const domRef = useRef<HTMLDivElement>(null);

    useEffect(()=>{
        if (domRef.current) {
            domRef.current.style.color = 'skyblue';
        }
    }, []);

    const storeRef = useRef<Store>(null);

    if (storeRef.current === null) {
        storeRef.current = new Store();
    }

    return <div ref={domRef}>
        {storeRef.current.get('key')}
    </div>
}

We use a way recommended by React to initialize the storeRef. The initialization will only occur once because we add a if block to control.

One of pros is that storeRef is populated with store during the first execution of component, making it available in the first render result. So we can call store.get('key') in JSX without telling if storeRef.current is null.

But the code above will throw an error:

TS tells us the storeRef.current is a read-only property, so we cannot change the value it holds.

Cause

Let's take a look at the type annotations of useRef. It would be very easy if you're using VSCode.



/**
* `useRef` returns a mutable ref object whose `.current` property is initialized to the passed argument
* (`initialValue`). The returned object will persist for the full lifetime of the component.
*
* Note that `useRef()` is useful for more than the `ref` attribute. It’s handy for keeping any mutable
* value around similar to how you’d use instance fields in classes.
*
* @version 16.8.0
* @see {@link https://react.dev/reference/react/useRef}
*/
function useRef<T>(initialValue: T): MutableRefObject<T>;
// convenience overload for refs given as a ref prop as they typically start with a null value
/**
* `useRef` returns a mutable ref object whose `.current` property is initialized to the passed argument
* (`initialValue`). The returned object will persist for the full lifetime of the component.
*
* Note that `useRef()` is useful for more than the `ref` attribute. It’s handy for keeping any mutable
* value around similar to how you’d use instance fields in classes.
*
* Usage note: if you need the result of useRef to be directly mutable, include `| null` in the type
* of the generic argument.
*
* @version 16.8.0
* @see {@link https://react.dev/reference/react/useRef}
*/
function useRef<T>(initialValue: T | null): RefObject<T>;

There are three overloads, and we only focus on the first two. We can tell by name that MutableRefObject is mutable, while RefObject is immutable.



interface MutableRefObject<T> {
    current: T;
}

interface RefObject<T> {
    readonly current: T | null;
}

It seems that we created a RefObject instead of MutableRefObject.

Let's recall the code we write and two overloads of useRef.



const storeRef = useRef<Store>(null);

function useRef<T>(initialValue: T): MutableRefObject<T>;

function useRef<T>(initialValue: T | null): RefObject<T>;

Obviously the generic type T is parsed to Store, and the argument we pass is null. The first overload doesn't match it but the second one does (because only the second overload accepts null type argument), so TS compiler ends up choosing the second one, resulting in a RefObject<Store>.

Solutions

Option 1

The type annotation package already tells you the solution:

Usage note: if you need the result of useRef to be directly mutable, include | null in the type.

So we can update the code and set the generic type of useRef to Store | null. I would remove the domRef related code to focus more on storeRef.



function App() {
    const storeRef = useRef<Store | null>(null);

    if (storeRef.current === null) {
        storeRef.current = new Store();
    }

    return <div>
        {storeRef.current.get('key')}
    </div>
}

It works. Take attention to the storeRef.current.get('key') in returned JSX, it doesn't throw any error although the type of store is set to Store | null. It's because the type guard of TS detects that in the if block, we assign a store value to storeRef.current. TS compiler knows that after the if block, the storeRef.current would be Store forever.

But if we use storeRef.current in elsewhere without type guard, there will be an error.



function App() {    
    const storeRef = useRef<Store | null>(null);

    if (storeRef.current === null) {
        storeRef.current = new Store();
    }

    useEffect(() => {
        const value = storeRef.current.get('key'); // without narrowing of TS
        console.log(value);
    }, []);

    return <div>
        {storeRef.current.get('key')}
    </div>
}

We can update the code simply by adding a protection:



function App() {    
    const storeRef = useRef<Store | null>(null);

    if (storeRef.current === null) {
        storeRef.current = new Store();
    }

    useEffect(() => {
        if (storeRef.current) {
            const value = storeRef.current.get('key'); // OK
            console.log(value);
        }
    }, []);

    useEffect(() => {
        const value = storeRef.current?.get('key'); // OK, but the value type would be `undefined | ReturnType<typeof get>`
        console.log(value);
    }, []);

    useEffect(() => {
        const value = storeRef.current!.get('key'); // OK, and the value type would be `ReturnType<typeof get>`
        console.log(value);
    }, []);


    return <div>
        {storeRef.current.get('key')}
    </div>
}

There are three ways to solve the error. Notice the second one, the type of value would be undefined | ReturnType<typeof get> because TS compiler doesn't know storeRef.current would never be null. TS thinks it might be null and the whole expression might return undefined in advance. So we may need to add type protection for value again.

The third one is good. The value type is ReturnType<typeof get>, so there is no need to add type protection for it again. Easy! But there is still an annoying thing: we need to add ! behind storeRef.current everywhere.

Option 2

To avoid adding ! everywhere, we could add it behind null passed to useRef.



function App() {    
    const storeRef = useRef<Store>(null!); // 1. remove `null` type. 2. add ! behind `null` argument

    if (storeRef.current === null) {
        storeRef.current = new Store();
    }

    useEffect(() => {
        const value = storeRef.current.get('key'); // without narrowing of TS
        console.log(value);
    }, []);

    return <div>
        {storeRef.current.get('key')}
    </div>
}

This is perfect. We set the generic type to Store, so TS knows that storeRef.current can only be Store. And we add a ! behind null argument, which tells TS the value will not be null at runtime.

Personally, I would prefer option 2 as it requires less code. But keep in mind that you can only do it when you're absolutely sure that the value will not be null at runtime. Otherwise a runtime error may bother you later. In this scenario, it's safe because we initialize storeRef.current instantly after the declaration.

Understand lifetime as a Rust beginner

Arc — Sun, 17 Mar 2024 10:26:50 +0000

If you're new to Rust like me, you're pretty likely to get confused by lifetime. So I'm writing this article to record some confusing points and answers.

I'm not going to illustrate some very basic concepts such as dangling pointer, heap and stack, ownership, etcetera. Please make sure you're familiar with them.

Retrospect

As we all know, lifetime is actually the scope of a value. When a value leaves its scope, it will get dropped. And you've seen the tutorial code lots of times:

fn longest(x: &str, y: &str) -> &str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

It's a piece of classic demo code to illustrate lifetime. The code will fail to compile because compiler does not know the relationships between x, y, and return value. So you need to add lifetime annotations manually:

fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

Why compiler needs to know the relationships?

That's the first question in my mind. In other language like TypeScript, we can write the longest function in a very simple form. Because all types we talk about in this article are references while string is not a reference type in JavaScript, we use array instead:

function longest(a: any[], b: any[]): any[] {
    if (a.length > b.length) {
        return a;
    } else {
        return b;
    }
}

It seems that we and TS compiler/ JS engine does not need to know the relationship. But Rust has a very strict mechanism to ensure memory safety:

A value only has one owner, and a value will get dropped when getting out of scope.

Considering a function which takes one or more reference arguments and returns a reference, the returned reference can only either be from arguments, or have a static lifetime. Because if the returned reference points to a value in the function, the value will get dropped at the end of function, which makes the returned reference a dangling pointer (points to a dropped value).

So, let's ignore static lifetime for now. The answer for why compiler needs to know the relationships between arguments (references) and return value (reference), is that the return value must come from arguments, and compiler has to check if it's valid by borrow checker.

Borrow Checker

Rust uses borrow checker to check if the reference is valid. In short, borrow checker checks if the reference lives shorter than the referenced value for the sake of avoiding dangling pointers. Lifetime annotations are actually to assist borrow checker. They tell borrow checker the specific rules to follow and execute the check process.

And I found there is a confusing point in the ubiquitous demo code longest. The &str values usually have a static lifetime by default. That's to say, the code below would get compiled and run successfully:

let str1 = "hello"; // str1 has a static lifetime
let res: &str;

{
    let str2 = "myworld"; // str2 has a static lifetime
    res = longest(str1, str2);
} // str2 will not be dropped here

println!("{}", res); // myworld

It might be a little bit confusing. So I would use &i32 instead of &str to explain in the following part.

Perspective of Function Caller

Let's observe the code at the perspective of caller:

fn main() {
    let x: i32 = 13;
    let res: &i32;
    {
        let y: i32 = 6;
        res = biggest(&x, &y); // Would it be res = &x ? or res = &y ? or res = SomeStruct { x: &x, y:&y }? It's unclear.
    }
}

Imagine you're the Rust compiler. Now, please tell me, do you allow the compilation? You cannot make the decision because you don't know the res is from x, or from y, or both (in a struct type containing both x and y ). Your borrow checker does not know what rules to follow and check. It only knows reference cannot outlive referenced value, and now res is absolutely reference, but who is the referenced value? x or y? Should I check if res outlives x ? Or should I check if res outlives y ? You may choose to check if both x and y outlive res, but what if the biggest function only returns x while y is just a message to be printed? In this case y does not need any lifetime restriction but you add one. It's too arbitrary.

That's why we need lifetime annotations.

fn biggest<'a>(x: &'a i32, y: &'a i32) -> &'a i32 {
    if x > y {
        x
    } else {
        y
    }
}

Now, Rust compiler knows that x , y, return value are all related to lifetime 'a . There are many explanations about the word related like:

x has a lifetime more than 'a , y has a lifetime more than 'a , while return value has a lifetime which is exactly 'a.

That makes sense. And IMO we can memorize it in a simple way:

return value has a lifetime 'a, while x and y should both have a lifetime longer than 'a.

That's what I think the most close explanation to how Rust compiler thinks. Let's consider the following code:

let x: i32 = 13;

let res: &i32;

{
    let y: i32 = 6;
    res = biggest(&x, &y);
}

println!("{}", res)

It would fail to compile and compiler would throw the error:

b does not live long enough

It's because we tell compiler the relationships between x, y, and res by lifetime annotations: both x and y should outlive res. So compiler would check as the rule.

If x outlives res? Yes, they have the same scope.
If y outlives res? No, lifetime of res is longer than y. Refuse to compile.

Variants

Let's see what will happen if we try some other lifetime annotations and return value.

Variant 1

fn biggest_variant1_incorrect<'a, 'b>(x: &'a i32, y: &'b i32) -> &'a i32 {
    if x > y {
        x
    } else {
        y
    }
}

Check Rules we tell compiler:

x should outlive res.

The code would fail to compile with an error message:

error: lifetime may not live long enough
function was supposed to return data with lifetime 'a but it is returning data with lifetime 'b

Please pay attention to the word may not. It means the compiler does not know if y could outlive res . It may be, or it may not be. It's unclear because lifetime 'b has nothing to do with 'a . We only tell compiler x should outlive res, but we may return y. Compiler does not know the rule about y.

Since we need to tell compiler that y must outlive res:

fn biggest_variant1_correct<'a, 'b: 'a>(x: &'a i32, y: &'b i32) -> &'a i32 {
    if x > y {
        x
    } else {
        y
    }
}

'b: 'a means 'b outlives 'a . It looks like the generics. If you say T: Debug, it means generic T must has the trait Debug.

Now compiler knows that 'b outlives 'a and compile it successfully.

Variant 2

fn say_something_and_echo<'a, 'b>(x: &'a i32, y: &'b i32) -> &'a i32 {
    println!("say {}", y);

    y
}

Check Rules we tell compiler:

x should outlive res.

The compiler would throw the same error as variant 1, because compiler does not know the rules between real return value y with lifetime 'b and 'a in function signature. We need to add 'b: 'a as well.

Trifles

The same scenario in JS

Let's take a look at the JS code which fails to compile in Rust:

const arr1 = [1, 2, 3];
let res = [];
{
  const arr2 = [1, 2, 3, 4];
  res = longest(arr1, arr2);
} // arr2 does not get dropped
console.log(res); // [1, 2, 3, 4]

JS value will not be freed or dropped after leaving its scope. It's a rule just in Rust. So JS does not need to consider about whatever lifetimes. It uses GC to manage memory. arr2 is referenced by res, so it will not be dropped.

Static lifetime

Values with a static lifetime will survive along with the process. That's why the code would compile successfully:

let str1 = "hello"; // str1 has a static lifetime
let res: &str;

{
    let str2 = "myworld"; // str2 has a static lifetime
    res = longest(str1, str2);
} // str2 will not be dropped here

println!("{}", res); // myworld

Since they live all the time, why we still need lifetime annotations in longest? It's because &str is not always static.

let string1: String = "hello".to_string();
let string1_ref: &str = &string1;

let res: &str;


{
    let string2 = "myworld".to_string();
    let string2_ref: &str = &string2;

    res = longest(&string1, &string2); // error: `string2` does not live long enough
} // string2 gets dropped here, so string2_ref is invalid

println!("{}", res);

In Rust, you can assign a &String to &str like we do above (remember longest takes two &str arguments). In the above case, string2_ref will be invalid after getting out of scope.

Summary

Rust uses borrow checker to check if references are valid. But when it meets a function which takes references as input and reference as output, it does not know the rules to check.
The purpose of lifetime annotations are to tell borrow checker the rules to follow, so that borrow checker would know what values to check and how to check them.
fn function<'a>(input1: &'a type, input2: &'a type) -> &'a type specifies the rule: return value has a lifetime 'a, while both input1 and input2 must have a lifetime longer than (or equal as) 'a.
Lifetime annotations will not affect the real lifetime of values. They just help compiler.

In a word, lifetime annotations tell borrow checker the rules to check in some unclear situations, while borrow checker perform the actual checking process

Build a simple VPN via socks 5 from scratch

Arc — Mon, 11 Mar 2024 16:25:47 +0000

Preface

This article will explore ways to develop a simple version of shadowsocks.

Because I'm not very familiar with networks, there may be some errors in it. Please feel free to point out them.

This article is for beginners and may be superficial.

This article only focuses on communications over TCP, not including UDP.

This article requires the basic knowledge of:

JavaScript
Node.js
HTTP

About Buffer

The computer handles binary data at low level, the same as the progress of network transmission.

Node.js offers the Buffer class to handle binary data. A buffer object is like an array with a byte as an item (usually displayed as hex). Here are some frequently-used operations below (the encoding of chars are not under consideration in the series, UTF-8 by default):

Buffer.from("hello")

Returns <Buffer 68 65 6c 6c 6f> , and every item is the ASCII code of the char.

Buffer.from([0x00, 0x01, 0x02])

Returns <Buffer 01 02 03> , and every item is a byte.

buffer.slice() Just like the slice of arrays, it splits a part of buffer and returns that.
buffer.toString() Transform the buffer to string, and every one/multiple bytes represent a char.
buffer.toJSON() Transform the buffer to a JSON object, and every item is a decimal number if printed. This is useful when handling blank chars like \r \n because they may not be visible in some logs.

let buf = Buffer.from("hello"); // <Buffer 68 65 6c 6c 6f>
console.log(buf.slice(0, 3).toString()); // "hel"
console.log(buf.toJSON()); // { type: 'Buffer', data: [ 104, 101, 108, 108, 111 ] }

About TCP

As a frontend engineer, we should be very familiar with HTTP. Whether sending HTTP requests or using express , koa to develop an HTTP server, we're using HTTP.
But maybe we're not so familiar with TCP. Now I'll introduce how to develop a TCP server and a TCP client in Node.js simply.

Server

// server.js
const net = require('net');

const server = net.createServer((socket) => {
  socket.on('data', (data) => {
    console.log('data from client:', data);
    socket.write('Hello from server.');
  });
});

server.listen(4001);

Client

// client.js
const net = require('net');

const socket = net.connect(4001, '127.0.0.1', () => {
  socket.write('Hello from client');
});

socket.on('data', (data) => {
  console.log('data from server:', data);
});

As shown in the figure, the createServer method of net module is actually to create a TCP server. The TCP server and client use a pair of socket to communicate with each other. Socket is a duplex, which is a readable and writeable stream. If call sockatA.write(data), socketB would receive data.

Let's run node server.js , and then run node client.js. The result is below:

According the the introduce of Buffer in last article, we know that server received the message from client: Hello from client, and sent a message Hello from server to client, in a way of TPC transmission.

Understanding the relationship between TCP and HTTP

As is known to us, TCP/IP is based on the 4 layers model, and HTTP is at the application layer while TCP is at the transport layer.
HTTP is based on TCP

How to understand the phrase based on?

Let's build a TCP server:

// server.js
const net = require('net');

const server = net.createServer((socket) => {
  socket.on('data', (data) => {
    console.log(data.toString());
  });
});

server.listen(4001);

Then we we visit localhost:4001 on browser, the console would print logs as below:

The server received a string with an HTTP request message content. In the meanwhile, the browser will be loading status because server does not return any response.

Let's update server code to return an HTTP response:

// server.js
const net = require('net');

const server = net.createServer((socket) => {
  socket.on('data', (data) => {
    console.log(data.toString());
    const html = `
    <!DOCTYPE html>
    <html>
        <head>
          <title>hello</title>
        </head>
        <body>
          <div style="color:skyblue;">hello world</div>
        <body
      </html>`;

    const body = Buffer.from(html); // body is for calculating length

    const rawResponse =
      'HTTP/1.1 200 OK\r\n' +
      'Content-Type: text/html\r\n' +
      `Content-Length: ${html.length}\r\n` +
      '\r\n\r\n' +
      body;

    socket.write(rawResponse);
  });
});

server.listen(4001);

Now we visit it again:

It shows the html content in response. That's the essence of HTTP: a request has a corresponding response, while they are both text.

Overall, TCP is a protocol to control transmission. However, it does not care the detail of transmitted content. The detail is controlled by the high level (application) protocols, such as HTTP. Similarly, client and server usually use JSON to communicate with each other. The JSON format is just a "protocol" based on HTTP.

Besides, the port of HTTP is actually the port of TCP.

About proxy and socks5

Proxy is a middleware server. Let's call client C, server S, proxy P. The relationship of them is like:

The job of proxy is to forward data. Assume there are some barriers between C and S (like the Great Fire Wall) forbidding the communication, but C and P, P and S could communicate freely, then we can use P to help the communication between C and S.

socks5 is a proxy protocol between the application layer and transport layer, so socks5 uses TCP to transmit HTTP message.

Let's take the basic socks5 communication without authentication as an example:

client sends a handshake message：

                   +----+----------+----------+
                   |VER | NMETHODS | METHODS  |
                   +----+----------+----------+
                   | 1  |    1     | 1 to 255 |
                   +----+----------+----------+

The number in second line is neither value nor number range but length. The number 1 under VER indicates that the length of VER is 1 byte. The length of METHODS is from 1 to 255 bytes.

1st byte: VER, is the version number. For socks5, the value is 0x05.
2nd byte: NMETHODS, is the count of supported authentication methods by client.
From the 3rd byte, every byte represents an authentication method.

Because the data is binary and is read as byte one by one, it's crucial to distinguish the boundaries. So we use a specific byte to represent the length n of a field, and use the following n byte(s) to represent the value of the field, which is a very common way.

For example, considering the string 127.0.0.14000, it takes 13 bytes. The program cannot tell which part is ip and which is port when reading it. But given the string 09127.0.0.14000with a rule: the former 2 bytes represent the length of ip, it's easy to tell that 127.0.0.1 is ip while 4000 is port because it says the first 9 bytes is ip.

proxy returns a response：


                         +----+--------+
                         |VER | METHOD |
                         +----+--------+
                         | 1  |   1    |
                         +----+--------+

1st byte: the same, 0x05。
2nd byte: METHOD, is the authentication method chosen by server. 0x00 means that it does not need any authentication.

client sends a request：

        +----+-----+-------+------+----------+----------+
        |VER | CMD |  RSV  | ATYP | DST.ADDR | DST.PORT |
        +----+-----+-------+------+----------+----------+
        | 1  |  1  | X'00' |  1   | Variable |    2     |
        +----+-----+-------+------+----------+----------+

After the connection via handshake, client is going to send requests to proxy. Since it's a proxy, client needs to tell proxy the target ip and port it wants the data to be sent to. Otherwise proxy does not know where to forward data.

VER: same.
CMD: the command of the socks session
- 0x01 CONNECT. We'll only talk about it in this article.
- 0x02 BIND
- 0x03 UDP forward
RSV: reserved with a value 0x00
ATYP: the type of target server address. DST.ADDR is the ip while DST.PORT is the port.
- 0x01 means IPv4, with it DST.ADDR takes 4 bytes. For example, ATYP + DST.ADDR + DST.PORT: 01 c0 a8 01 01means the ip of target server is 192.168.1.1
- 0x03 means domain. Due to the unfixed length of domains, the length of DST.ADDR is unfixed as well. Remember how to transmit data with unfixed size? Yes, length first byte. So in this case, the first byte of DST.ADDR represents the length n of the domain , while the following n bytes represent domain. For example, ATYP + DST.ADDR + DST.PORT: 03 09 62 61 69 64 75 2e 63 6f 6d 01 bb means the domain is baidu.com, and the port is 443.
- 0x04 means IPv6. DST.ADDR takes 16 bytes.

proxy returns a response

        +----+-----+-------+------+----------+----------+
        |VER | REP |  RSV  | ATYP | BND.ADDR | BND.PORT |
        +----+-----+-------+------+----------+----------+
        | 1  |  1  | X'00' |  1   | Variable |    2     |
        +----+-----+-------+------+----------+----------+

REP: response status. 0x00 means success.
ATYPE: address type of proxy .
BND.ADDR is the ip of proxy，BND.PORT is the port.

BND.ADDR and BND.PORT is the ip address and port of proxy, not target server. Proxy uses this ip-port to communicate with target server. For connect command, the 2 values could be set to 0 in basic scenario because client does not care which ip-port is used by proxy to communicate with server.

start forwarding data After the initialize process above, client would send the real data to proxy, while proxy forwards it to target server. In a similar way, target server would send the response to proxy, while proxy forwards to client. These forwarding processes are just via TCP protocol we talked above.

Demo Code

In the demo, we only focus on CONNECT command with IPv4 and domain.

const net = require('net');

const port = 4000;

const STATE = {
  INIT: 0,
  SENT_FIRST_HANDSHAKE_RESPONSE: 1,
  ERR: -1,
};

const server = net.createServer((socket) => {
  let state = STATE.INIT;

  const closeSocket = () => {
    socket.destroy();
    state = STATE.ERR;
  };

  socket.on('data', (data) => {
    switch (state) {
      case STATE.INIT: // initial state, ready to receive the 1st handshake message
        const version = data.readUInt8(0); // the first byte is VER (version)
        if (version !== 5) { // VER must be 0x05
          closeSocket();
          return;
        }

        socket.write(Buffer.from([0x05, 0x00])); // return 0x0500 which means no need for authentication
        state = STATE.SENT_FIRST_HANDSHAKE_RESPONSE;
        break;

      case STATE.SENT_FIRST_HANDSHAKE_RESPONSE: // already received the 1st handshake message, now ready to receive CONNECT message including target server address, port, etc.
        const cmd = data.readUInt8(1);

        if (cmd !== 1) {
          Buffer.from([
            0x05, 0x07, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
          ]); // received unsupported CMD, tell client failure
          closeSocket();
          return;
        }

        // read ip-port of target server
        let addrType = data.readUInt8(3);
        let addrLength, remoteAddr, remotePort;

        if (addrType === 4) {
          // unsupported IPv6 type

          socket.write(
            Buffer.from([
              0x05, 0x08, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
            ])
          );
          closeSocket();
          return;
        }

        if (addrType === 3) {
          // domain
          addrLength = data.readUInt8(4);
          remoteAddr = data.slice(5, 5 + addrLength).toString();
          remotePort = data.readUInt16BE(data.length - 2);
        } else if (addrType === 1) {
          // ipv4
          remoteAddr = data.slice(4, 8).join('.');
          remotePort = data.readUInt16BE(data.length - 2);
        }

        // 连接 target server
        const remote = net.createConnection(
          { host: remoteAddr, port: remotePort },
          () => {
            socket.write(
              Buffer.from([
                0x05, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
              ])
            ); // tell client success

            state = STATE.SENT_CONNECT_RESPONSE;

            console.log(`connecting ${remoteAddr}:${remotePort}`);
            // KEY POINT: pipe two sockets to forward
            socket.pipe(remote);
            remote.pipe(socket);
          }
        );

        remote.on('error', (err) => {
          remote.destroy();
          closeSocket();
        });

        break;
    }
  });

  socket.on('error', (err) => {
    console.log('socket error', err.message);
  });
});

server.listen(port, () => {
  console.log(`socks5 proxy server is listening on port ${port}`);
});

The key point:

socket.pipe(remote);
remote.pipe(socket);

is just like:

socket.on('data', data => remote.write(data));
remote.on('data', data => socket.write(data));

Unlike HTTP server handling string in most cases, TCP server handles Buffer. So for data, we need to call some Buffer methods.

Deploy it on a server which is accessible to both target server(like Google) and your client, and configure your client proxy settings to connect it, then you'll be free to have access to Google!

Full code available on https://github.com/Arichy/arcsocks

Forem: Arc

Guard Your Rust Code with Tests

Property Testing

Differential Testing

Snapshot Testing

Summary

Rust Data Structures - Skip List

Rust Data Structures - Skip List

Structure of a Skip List

Randomness

Optimization for Random Access

Data Structure

Insertion

Deletion

Search

Memory Management

Performance Comparison

Conclusion

Complete Code

Rust Data Structures - Red-Black Tree

1. Introduction to Red-Black Trees

1.1 Binary Search Tree (BST)

1.2 Rules of Red-Black Trees

2. Introduction to Red-Black Tree Operations

2.1 Recoloring

2.2 Rotation

3. Search

4. Insertion

4.1 Parent P is Black

4.2 Parent P is Red

4.2.1 Uncle U is Red

4.2.2 U is Black

5. Deletion

5.1 Deleted Node is Red

5.2 Deleted Node is Black

5.2.1: X's Sibling S is Red

5.2.2: X's Sibling S is Black

5.2.2.1: S is black, and both its children (FN, NN) are also black

5.2.2.2: S is black, FN (Far Nephew) is red

5.2.2.3: S is black, FN (Far Nephew) is black, NN (Near Nephew) is red

6. Rust Language-Specific Issues

6.1 Data Structure Design

6.2 Memory Management

7. Conclusion

8. Complete Code

A Journey From JS To Rust

0. Pronunciation

Keywords/Syntax Elements

Types/Structs

1. Basic Content: mut

2. Advanced Content: Hello World

2.1. Strings

2.2. Macro

3. Array vs Vec

4. Enum and Pattern Matching

4.1. Potentially Null Values: Option<T>

4.2. Error Handling: Result<T, E>

4.3. unwrap

5. Trait

6. Closures vs Functions

6.1. Capture by Reference vs Capture by Ownership

7. Multithreading and Async

7.1. Multithreading

7.2. Async

8. Forgetting Object-Oriented Programming

8.1. The Essence of Method Calls

8.2. Generics for Parametric Polymorphism

8.3. Trait Objects for Subtype Polymorphism

1. Static Construction at Compile Time

2. Pointer Combination at Runtime

8.4. Traits for Ad-Hoc Polymorphism

Summary

Pin in Rust: The Why and How of Immovable Memory

Why Pin is needed

The danger Self-Referential struct

The essential of async/await

Pin/Unpin

The essential of Pin

Summary

Using gRPC in React the Modern Way: From gRPC-web to Connect

1. Basic Content: `mut`

4.1. Potentially Null Values: `Option<T>`

4.2. Error Handling: `Result<T, E>`

4.3. `unwrap`