Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Encoding TCP in Rust’s Type System, Part 2: Placeholder Values Are Not Our Friends

November 14, 2026


In this post, I’ll continue on from Part 1 to discuss another example of how I used Rust’s type system to enforce correctness while implementing TCP/IP in my project Typenet. Although I recommend reading in order, the core concepts of this post are independent, so it may be digestible standalone, especially if you’re already somewhat familiar with TCP.

The part of the project I’d like to focus on here is updating the TCP send window. In particular, there was a subtle bug that was only possible because I had used placeholder zero values where the true state was not zero, but no state at all. In a structure similar to that of Part 1, I’ll explain the problem before going level by level through increasingly type-safe designs.

Table of Contents

  1. The Problem at Hand
  2. The Source of the Bug
  3. Level 0: Just Fix the Bug
  4. Level 1: Make the Fields Optional
  5. Level 2: One Option for All Three Fields
  6. Level 3: WindowState in TcpState Variants
  7. Level 4: The Typestate Pattern
  8. Conclusion

The Problem at Hand

The send window is used to keep track of how much data a TCP peer is willing to receive. The window-related state comprises three values maintained locally for each connection, SND.WND, SND.WL1, and SND.WL2. Upon receiving an appropriate segment (SEG.* below) on an established connection, a set of conditions is checked against the current send state (SND.* below) to potentially update the three window state values.

Variable meanings (click to expand)

Definitions from RFC 9293, Section 3.4:

  • SND.NXT: next sequence number to be sent
  • RCV.NXT: next sequence number expected on an incoming segment
  • SND.UNA: oldest unacknowledged sequence number

And from Section 4:

  • SND.WND (send window): This represents the sequence numbers that the remote (receiving) TCP endpoint is willing to receive… The range of new sequence numbers that may be emitted by a TCP implementation lies between SND.NXT and SND.UNA + SND.WND - 1.
  • SND.WL1: segment sequence number at last window update
  • SND.WL2: segment acknowledgment number at last window update

The pseudocode below is adapted from RFC 9293, Section 3.10.7.4 (specific paragraph linked). It is essentially checking that the incoming window value is fresh, rather than being a stale value from a reordered or retransmitted segment.

Crucially, the comparisons here are based on serial number arithmetic, as I explained in more detail in Part 1. Although RFC 9293 uses < and =<1 for circular inequalities, I use precedes and precedes_or_eq here to avoid confusion with linear inequalities.

p = precedes
pe = precedes_or_eq

if SND.UNA pe SEG.ACK && SEG.ACK pe SND.NXT
    && (SND.WL1 p SEG.SEQ || (SND.WL1 == SEG.SEQ && SND.WL2 pe SEG.ACK))
{
    SND.WND = SEG.WND
    SND.WL1 = SEG.SEQ
    SND.WL2 = SEG.ACK
}

The Source of the Bug

According to RFC 9293, Section 3.10.7.4 (specific paragraph for passive open linked), the three window values are only set upon establishing a connection, and not before that while the initial handshake is in progress.

Below is a significantly pared-down version of how I was representing the connection state and performing the update. The update function used throughout this post only covers the second part of the condition above, SND.WL1 p SEG.SEQ || (SND.WL1 == SEG.SEQ && SND.WL2 pe SEG.ACK), because that is the part affected by the window state representation. establish is similarly stripped down for illustrative purposes.

Note

  • I explain SeqPoint and SeqOffset in Part 1, but understanding them in detail is not required for the point I’m making here.
  • Part 1 did not include Direction::Rev. This refers to the reverse direction, i.e. In::Rev is Out and Out::Rev is In.
  • On any code block, click the eye symbol to show its hidden lines, or the play button to run it.
#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived,
    Established,
    /* Other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self {
        Self {
            tcp_state: TcpState::SynReceived,
            // The offending placeholder zeros
            snd_wnd: SeqOffset::new(0),
            snd_wl1: SeqPoint::new(0),
            snd_wl2: SeqPoint::new(0),
        }
    }

    fn establish(mut self, seg: TcpSegment<In>) -> Self {
        self.tcp_state = TcpState::Established;
        self.update(seg) // Incorrect, should be set unconditionally
    }

    fn update(self, seg: TcpSegment<In>) -> Self {
        if self.snd_wl1.precedes(seg.seq_num)
            || (self.snd_wl1 == seg.seq_num
                && self.snd_wl2.precedes_or_eq(seg.ack_num))
        {
            Self {
                tcp_state: self.tcp_state,
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            }
        } else {
            self
        }
    }
}

let handshake_completing_ack = TcpSegment {
    seq_num: SeqPoint::new(24),
    ack_num: SeqPoint::new(42),
    window: SeqOffset::new(0xFFFF),
};

let established_conn = ConnState {
    tcp_state: TcpState::Established,
    snd_wnd: handshake_completing_ack.window,
    snd_wl1: handshake_completing_ack.seq_num,
    snd_wl2: handshake_completing_ack.ack_num,
};

// Values small enough that the window state was set upon establishment anyway
assert_eq!(ConnState::new().establish(handshake_completing_ack), established_conn);

println!("Assertion passed (despite bug)!");
}

As is common practice in many other languages (and even some Rust), I used zero-initialization to create placeholders until real values arrived. Specifically, I did this for snd_wnd, snd_wl1, and snd_wl2 when the connection state was first recorded (SYN-RECEIVED), even including a comment that they were placeholders until the real values were set upon establishment. The appeal of this approach was its simplicity, but as is evidenced here, manually remembering when values might be placeholders and when they’re real values can be more error-prone than it’s worth. Instead of unconditionally setting them upon establishment as I should have, I called update as is done for established connections. That resulted in meaningless zeros being used in the comparisons.

This bug was particularly subtle because it only produced an incorrect result when zero was being compared against SEG.SEQ values that were at least (1 << 31) + 1 (which zero does not precede in serial number arithmetic). For values up to and including 1 << 31, the condition was true and the window state was correctly set. For values greater than 1 << 31, the condition would have been false, leaving the window state variables incorrectly set to zeros, but tests used small values so that they were easier to reason about manually, allowing this bug to get through.

#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived,
    Established,
    /* Other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self {
        Self {
            tcp_state: TcpState::SynReceived,
            // The offending placeholder zeros
            snd_wnd: SeqOffset::new(0),
            snd_wl1: SeqPoint::new(0),
            snd_wl2: SeqPoint::new(0),
        }
    }

    fn establish(mut self, seg: TcpSegment<In>) -> Self {
        self.tcp_state = TcpState::Established;
        self.update(seg) // Incorrect, should be set unconditionally
    }

    fn update(self, seg: TcpSegment<In>) -> Self {
        if self.snd_wl1.precedes(seg.seq_num)
            || (self.snd_wl1 == seg.seq_num
                && self.snd_wl2.precedes_or_eq(seg.ack_num))
        {
            Self {
                tcp_state: self.tcp_state,
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            }
        } else {
            self
        }
    }
}

let handshake_completing_ack = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

let established_conn = ConnState {
    tcp_state: TcpState::Established,
    snd_wnd: handshake_completing_ack.window,
    snd_wl1: handshake_completing_ack.seq_num,
    snd_wl2: handshake_completing_ack.ack_num,
};

// Bug verified! Should be equal
assert_ne!(ConnState::new().establish(handshake_completing_ack), established_conn);

// Window state was left at zero instead of being set upon establishment
assert_eq!(
    ConnState::new().establish(handshake_completing_ack),
    ConnState {
        tcp_state: TcpState::Established,
        snd_wnd: SeqOffset::new(0),
        snd_wl1: SeqPoint::new(0),
        snd_wl2: SeqPoint::new(0),
    }
);

println!("Assertions passed (incorrect behavior verified)!");
}

Level 0: Just Fix the Bug

My first step was simply to write a test using sufficiently large values, watch it fail, and then set snd_wnd: seg.window, snd_wl1: seg.seq_num, and snd_wl2: seg.ack_num unconditionally upon connection establishment instead of calling update, making the test pass. This fixed the bug and directly did what the RFC says.

#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived,
    Established,
    /* Other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self {
        Self {
            tcp_state: TcpState::SynReceived,
            snd_wnd: SeqOffset::new(0),
            snd_wl1: SeqPoint::new(0),
            snd_wl2: SeqPoint::new(0),
        }
    }

    fn establish(self, seg: TcpSegment<In>) -> Self {
        Self {
            tcp_state: TcpState::Established,
            snd_wnd: seg.window,
            snd_wl1: seg.seq_num,
            snd_wl2: seg.ack_num,
        }
    }

    fn update(self, seg: TcpSegment<In>) -> Self {
        if self.snd_wl1.precedes(seg.seq_num)
            || (self.snd_wl1 == seg.seq_num
                && self.snd_wl2.precedes_or_eq(seg.ack_num))
        {
            Self {
                tcp_state: self.tcp_state,
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            }
        } else {
            self
        }
    }
}

let handshake_completing_ack = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

assert_eq!(
    ConnState::new().establish(handshake_completing_ack),
    ConnState {
        tcp_state: TcpState::Established,
        snd_wnd: handshake_completing_ack.window,
        snd_wl1: handshake_completing_ack.seq_num,
        snd_wl2: handshake_completing_ack.ack_num,
    }
);

println!("Assertion passed!");
}

Even though that squashed the bug and tested the correct behavior, it didn’t make all bugs like it categorically impossible.

In a more abstract sense, these values are not zero before establishment. They don’t exist at all. Zero is an arbitrary value that just kind of seems like “we don’t have a value yet,” but it can be incorrectly used anywhere a real value can, and a real value can be zero. Furthermore, even though zero is the minimum bit pattern, that is really just an artifact of the physical representation, since sequence space is conceptually circular and doesn’t give any point special treatment as the minimum.

Level 1: Make the Fields Optional

The more structural fix was to correctly represent “no value” by using Option. Unlike arbitrary zeros, None accurately represented the state of the window variables before establishment, and the type system made silent misuse impossible.

#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived,
    Established,
    /* Other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    snd_wnd: Option<SeqOffset<Out>>,
    snd_wl1: Option<SeqPoint<In>>,
    snd_wl2: Option<SeqPoint<Out>>,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self {
        Self {
            tcp_state: TcpState::SynReceived,
            snd_wnd: None,
            snd_wl1: None,
            snd_wl2: None,
        }
    }

    fn establish(self, seg: TcpSegment<In>) -> Self {
        Self {
            tcp_state: TcpState::Established,
            snd_wnd: Some(seg.window),
            snd_wl1: Some(seg.seq_num),
            snd_wl2: Some(seg.ack_num),
        }
    }

    fn buggy_establish(mut self, seg: TcpSegment<In>) -> Result<Self, &'static str> {
        self.tcp_state = TcpState::Established;
        self.update(seg) // Incorrect, should be set unconditionally
    }

    fn update(self, seg: TcpSegment<In>) -> Result<Self, &'static str> {
        let Some(snd_wl1) = self.snd_wl1 else {
            return Err("`update` called with uninitialized SND.WL1");
        };
        let Some(snd_wl2) = self.snd_wl2 else {
            return Err("`update` called with uninitialized SND.WL2");
        };

        Ok(
            if snd_wl1.precedes(seg.seq_num)
                || (snd_wl1 == seg.seq_num && snd_wl2.precedes_or_eq(seg.ack_num))
            {
                Self {
                    tcp_state: self.tcp_state,
                    snd_wnd: Some(seg.window),
                    snd_wl1: Some(seg.seq_num),
                    snd_wl2: Some(seg.ack_num),
                }
            } else {
                self
            },
        )
    }
}

let handshake_completing_ack = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

assert_eq!(
    ConnState::new().establish(handshake_completing_ack),
    ConnState {
        tcp_state: TcpState::Established,
        snd_wnd: Some(handshake_completing_ack.window),
        snd_wl1: Some(handshake_completing_ack.seq_num),
        snd_wl2: Some(handshake_completing_ack.ack_num),
    }
);

use std::assert_matches;

assert_matches!(ConnState::new().buggy_establish(handshake_completing_ack), Err(_));

println!("Assertions passed!");
}

With this change, the same mistake correctly produced an error instead of silently using zeros, and this was enforced at the type level rather than being a one-off logic fix.

Wrapping the existing fields in Option was a step in the right direction, but was not quite right. These three pieces of state are not independently optional, but rather collectively begin with no values and then all get values upon connection establishment.

Level 2: One Option for All Three Fields

I therefore moved the three fields into a separate WindowState struct wrapped in a single Option, which was both more correct and more ergonomic.

#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived,
    Established,
    /* Other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct WindowState {
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    window_state: Option<WindowState>,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self { Self { tcp_state: TcpState::SynReceived, window_state: None } }

    fn establish(self, seg: TcpSegment<In>) -> Self {
        Self {
            tcp_state: TcpState::Established,
            window_state: Some(WindowState {
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            }),
        }
    }

    fn buggy_establish(mut self, seg: TcpSegment<In>) -> Result<Self, &'static str> {
        self.tcp_state = TcpState::Established;
        self.update(seg) // Incorrect, should be set unconditionally
    }

    fn update(self, seg: TcpSegment<In>) -> Result<Self, &'static str> {
        let Some(window_state) = &self.window_state else {
            return Err("`update` called with uninitialized window state");
        };

        Ok(
            if window_state.snd_wl1.precedes(seg.seq_num)
                || (window_state.snd_wl1 == seg.seq_num
                    && window_state.snd_wl2.precedes_or_eq(seg.ack_num))
            {
                Self {
                    tcp_state: self.tcp_state,
                    window_state: Some(WindowState {
                        snd_wnd: seg.window,
                        snd_wl1: seg.seq_num,
                        snd_wl2: seg.ack_num,
                    }),
                }
            } else {
                self
            },
        )
    }
}

let handshake_completing_ack = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

assert_eq!(
    ConnState::new().establish(handshake_completing_ack),
    ConnState {
        tcp_state: TcpState::Established,
        window_state: Some(WindowState {
            snd_wnd: handshake_completing_ack.window,
            snd_wl1: handshake_completing_ack.seq_num,
            snd_wl2: handshake_completing_ack.ack_num,
        }),
    }
);

use std::assert_matches;

assert_matches!(ConnState::new().buggy_establish(handshake_completing_ack), Err(_));

println!("Assertions passed!");
}

This way, it was impossible to erroneously set only a subset of the values to Some when they should all become known at the same time, and a single check for None or Some provided access to all three instead of requiring usage sites to check each of the fields individually.

This caught the bug and was more correct than the previous levels, but it needed to go further. There was only a single, predictable transition from None to Some, and it happened exactly at the transition from SYN-RECEIVED to ESTABLISHED, which was already being tracked in the tcp_state field of ConnState. In other words, the window state being None or Some was entirely determined by the TCP state being SYN-RECEIVED or ESTABLISHED (or states beyond ESTABLISHED also corresponding to Some).

Storing these pieces of state in two separate fields on ConnState meant that impossible combinations, such as a Some window state in SYN-RECEIVED or a None window state in ESTABLISHED, were representable, and the program had to handle them with no meaningful action to take.2

Level 3: WindowState in TcpState Variants

Accordingly, my next step was to unify the two fields by putting the WindowState data directly in TcpState::Established (and later synchronized states not shown here). A SYN-RECEIVED connection had no way of storing window state, and an ESTABLISHED connection couldn’t be created without real values read off the wire.

#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
struct WindowState {
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
}

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived,
    Established(WindowState),
    /* Other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self { Self { tcp_state: TcpState::SynReceived } }

    fn establish(self, seg: TcpSegment<In>) -> Self {
        Self {
            tcp_state: TcpState::Established(WindowState {
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            }),
        }
    }

    fn buggy_establish(self, seg: TcpSegment<In>) -> Result<Self, &'static str> {
        // No way to set the TCP state to `TcpState::Established` without (correctly)
        // getting the window state directly from the segment

        self.update(seg) // Incorrect, should be set unconditionally
    }

    fn update(self, seg: TcpSegment<In>) -> Result<Self, &'static str> {
        match self.tcp_state {
            TcpState::SynReceived => Err("`update` called in SYN-RECEIVED"),

            TcpState::Established(window_state) => Ok(
                if window_state.snd_wl1.precedes(seg.seq_num)
                    || (window_state.snd_wl1 == seg.seq_num
                        && window_state.snd_wl2.precedes_or_eq(seg.ack_num))
                {
                    Self {
                        tcp_state: TcpState::Established(WindowState {
                            snd_wnd: seg.window,
                            snd_wl1: seg.seq_num,
                            snd_wl2: seg.ack_num,
                        }),
                    }
                } else {
                    self
                },
            ),
        }
    }
}

let handshake_completing_ack = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

assert_eq!(
    ConnState::new().establish(handshake_completing_ack),
    ConnState {
        tcp_state: TcpState::Established(WindowState {
            snd_wnd: handshake_completing_ack.window,
            snd_wl1: handshake_completing_ack.seq_num,
            snd_wl2: handshake_completing_ack.ack_num,
        }),
    }
);

use std::assert_matches;

assert_matches!(ConnState::new().buggy_establish(handshake_completing_ack), Err(_));

println!("Assertions passed!");
}

This was another step in the right direction, but it still had some inconveniences and holes. Callers would match on the TCP state, find it to be TcpState::Established, and then call update, which was forced to internally check again for TcpState::Established to be able to access the window state, making update unnecessarily fallible. There was also nothing stopping a bug like calling establish when already in ESTABLISHED, unconditionally updating the window state instead of performing the necessary checks. For correctness purposes, establish really should have been fallible as well, returning Err if called from a state other than SYN-RECEIVED. However, that would have added another instance of the same ergonomic problem, repeating a check that the caller should have just done. Beyond the two states used for illustration in this post, the problematic pattern extended to any operation that was only valid in a proper subset of TCP states.

Level 4: The Typestate Pattern

I resolved these remaining issues with the venerable typestate pattern, defining a type for each TCP state so only the operations valid in that state would be possible.3

Note

Unlike in many typestate examples, the state types here are wrapped in the TcpState enum because ConnState is the value type for the HashMap connection table (not shown), where all connections must have the same type.

#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
struct WindowState {
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
}

#[derive(Debug, PartialEq, Eq)]
struct SynReceived;

#[derive(Debug, PartialEq, Eq)]
struct Established {
    window_state: WindowState,
}

/* Structs for other TCP states */

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived(SynReceived),
    Established(Established),
    /* Variants for other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self { Self { tcp_state: TcpState::SynReceived(SynReceived) } }
}

impl SynReceived {
    fn establish(self, seg: TcpSegment<In>) -> Established {
        Established {
            window_state: WindowState {
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            },
        }
    }
}

impl Established {
    fn update(self, seg: TcpSegment<In>) -> Self {
        if self.window_state.snd_wl1.precedes(seg.seq_num)
            || (self.window_state.snd_wl1 == seg.seq_num
                && self.window_state.snd_wl2.precedes_or_eq(seg.ack_num))
        {
            Self {
                window_state: WindowState {
                    snd_wnd: seg.window,
                    snd_wl1: seg.seq_num,
                    snd_wl2: seg.ack_num,
                },
            }
        } else {
            self
        }
    }
}


let syn_rcv_conn = ConnState::new();

let seg = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

// This is a fairly contrived example to keep the amount of code here manageable.
// In the codebase, the TCP state is already matched on for other processing,
// so it's simply a matter of using the inner struct already bound to `syn_rcv`,
// `established`, etc.
let established_conn = ConnState {
    tcp_state: TcpState::Established(match syn_rcv_conn.tcp_state {
        TcpState::SynReceived(syn_rcv) => syn_rcv.establish(seg),
        TcpState::Established(established) => established.update(seg),
    }),
};

assert_eq!(
    established_conn,
    ConnState {
        tcp_state: TcpState::Established(Established {
            window_state: WindowState {
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            },
        }),
    }
);

println!("Assertion passed!");
}

This way, one had to have a SynReceived struct and unconditionally set the window variables to get an Established struct, and one had to already have an Established struct to call update. Conversely, when these requirements were met, the operations were guaranteed to succeed. In other words, the impossible states issue from Level 2 was solved without introducing the redundant fallibility issue from Level 3.

There was no longer much of an error case to test, since the closest thing to the bugs of previous levels would be calling nonexistent methods, resulting in compile errors.

#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
struct WindowState {
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
}

#[derive(Debug, PartialEq, Eq)]
struct SynReceived;

#[derive(Debug, PartialEq, Eq)]
struct Established {
    window_state: WindowState,
}

/* Structs for other TCP states */

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived(SynReceived),
    Established(Established),
    /* Variants for other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self { Self { tcp_state: TcpState::SynReceived(SynReceived) } }
}

impl SynReceived {
    fn establish(self, seg: TcpSegment<In>) -> Established {
        Established {
            window_state: WindowState {
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            },
        }
    }
}

impl Established {
    fn update(self, seg: TcpSegment<In>) -> Self {
        if self.window_state.snd_wl1.precedes(seg.seq_num)
            || (self.window_state.snd_wl1 == seg.seq_num
                && self.window_state.snd_wl2.precedes_or_eq(seg.ack_num))
        {
            Self {
                window_state: WindowState {
                    snd_wnd: seg.window,
                    snd_wl1: seg.seq_num,
                    snd_wl2: seg.ack_num,
                },
            }
        } else {
            self
        }
    }
}


let seg = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

ConnState::new().establish(seg); // Only exists on `SynReceived`, not `ConnState`
}
#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
struct WindowState {
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
}

#[derive(Debug, PartialEq, Eq)]
struct SynReceived;

#[derive(Debug, PartialEq, Eq)]
struct Established {
    window_state: WindowState,
}

/* Structs for other TCP states */

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived(SynReceived),
    Established(Established),
    /* Variants for other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self { Self { tcp_state: TcpState::SynReceived(SynReceived) } }
}

impl SynReceived {
    fn establish(self, seg: TcpSegment<In>) -> Established {
        Established {
            window_state: WindowState {
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            },
        }
    }
}

impl Established {
    fn update(self, seg: TcpSegment<In>) -> Self {
        if self.window_state.snd_wl1.precedes(seg.seq_num)
            || (self.window_state.snd_wl1 == seg.seq_num
                && self.window_state.snd_wl2.precedes_or_eq(seg.ack_num))
        {
            Self {
                window_state: WindowState {
                    snd_wnd: seg.window,
                    snd_wl1: seg.seq_num,
                    snd_wl2: seg.ack_num,
                },
            }
        } else {
            self
        }
    }
}


let seg = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

ConnState::new().update(seg); // Only exists on `Established`, not `ConnState`
}

As a further benefit, making the inner structs neither Clone nor Copy and having state transition methods with self parameters (i.e. not &self) meant each state was consumed upon transitioning to another. This made it impossible to, for example, call SynReceived::establish but then accidentally keep using the original SynReceived (or a type containing it, as in the example below) instead of the new Established.4

#![allow(unused)]
fn main() {
use std::{fmt::Debug, marker::PhantomData, num::Wrapping, ops::Sub};

trait Direction: Debug + Clone + Copy + PartialEq + Eq {
    type Rev: Direction;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct In;

impl Direction for In {
    type Rev = Out;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct Out;

impl Direction for Out {
    type Rev = In;
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqPoint<D: Direction> {
    wrapping: Wrapping<u32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqPoint<D> {
    const fn new(primitive: u32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }

    fn precedes(self, other: Self) -> bool { (self - other).wrapping.0 < 0 }

    fn precedes_or_eq(self, other: Self) -> bool {
        self == other || self.precedes(other)
    }
}

impl<D: Direction> Sub for SeqPoint<D> {
    type Output = SeqOffset<D>;

    fn sub(self, rhs: Self) -> Self::Output {
        SeqOffset::new((self.wrapping - rhs.wrapping).0.cast_signed())
    }
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct SeqOffset<D: Direction> {
    wrapping: Wrapping<i32>,
    phantom: PhantomData<D>,
}

impl<D: Direction> SeqOffset<D> {
    fn new(primitive: i32) -> Self {
        Self { wrapping: Wrapping(primitive), phantom: PhantomData }
    }
}

#[derive(Clone, Copy)]
struct TcpSegment<D: Direction> {
    seq_num: SeqPoint<D>,
    ack_num: SeqPoint<D::Rev>,
    window: SeqOffset<D::Rev>,
    /* Other fields */
}

#[derive(Debug, PartialEq, Eq)]
struct WindowState {
    snd_wnd: SeqOffset<Out>,
    snd_wl1: SeqPoint<In>,
    snd_wl2: SeqPoint<Out>,
}

#[derive(Debug, PartialEq, Eq)]
struct SynReceived;

#[derive(Debug, PartialEq, Eq)]
struct Established {
    window_state: WindowState,
}

/* Structs for other TCP states */

#[derive(Debug, PartialEq, Eq)]
enum TcpState {
    SynReceived(SynReceived),
    Established(Established),
    /* Variants for other TCP states */
}

#[derive(Debug, PartialEq, Eq)]
struct ConnState {
    tcp_state: TcpState,
    /* Other fields */
}

impl ConnState {
    fn new() -> Self { Self { tcp_state: TcpState::SynReceived(SynReceived) } }
}

impl SynReceived {
    fn establish(self, seg: TcpSegment<In>) -> Established {
        Established {
            window_state: WindowState {
                snd_wnd: seg.window,
                snd_wl1: seg.seq_num,
                snd_wl2: seg.ack_num,
            },
        }
    }
}

impl Established {
    fn update(self, seg: TcpSegment<In>) -> Self {
        if self.window_state.snd_wl1.precedes(seg.seq_num)
            || (self.window_state.snd_wl1 == seg.seq_num
                && self.window_state.snd_wl2.precedes_or_eq(seg.ack_num))
        {
            Self {
                window_state: WindowState {
                    snd_wnd: seg.window,
                    snd_wl1: seg.seq_num,
                    snd_wl2: seg.ack_num,
                },
            }
        } else {
            self
        }
    }
}


let syn_rcv_conn = ConnState::new();

let seg = TcpSegment {
    seq_num: SeqPoint::new((1 << 31) + 24),
    ack_num: SeqPoint::new((1 << 31) + 42),
    window: SeqOffset::new(0xFFFF),
};

// `syn_rcv_conn` moved here
let established_conn = ConnState {
    tcp_state: TcpState::Established(match syn_rcv_conn.tcp_state {
        TcpState::SynReceived(syn_rcv) => syn_rcv.establish(seg),
        TcpState::Established(established) => established.update(seg),
    }),
};

fn use_conn(conn: ConnState) {}

use_conn(syn_rcv_conn); // Compile error, value was moved
}

Conclusion

At a surface level, the type representations of connection state got more complicated at each level in exchange for correctness guarantees. Given a ConnState in hand, Level 0 allowed easy access to the window variables as plain fields on that struct. Level 1 forced checks for None first, and Level 2 nested the fields in a separate WindowState struct. Level 3 put the WindowState behind a TcpState enum variant check, and Level 4 buried it deeper, adding an Established struct between the variant check and the WindowState field.

However, I think the trade-off is more nuanced than that, if it’s even a trade-off at all. The fact that window state variables are set upon connection synchronization is inherent to the task of implementing TCP, not additional complication from implementation decisions. It’s still there with a simpler implementation, just implicit and manual. Encoding it in the type system takes more work upfront, but removes the work of manually remembering it later.

At least in this case, making illegal states unrepresentable didn’t even amount to an ergonomic sacrifice. Call sites already needed to match on the TCP variant before deciding which of these methods to call, so matching on Level 4’s TcpState::Established(established) and then calling established.update(seg) wasn’t any more steps than the original conn.update(seg). While the intermediate levels (1, 2, and 3) forced one or more checks for whether the window state was initialized, making update correct but fallible, the typestate approach statically guaranteed that the error case was impossible, improving ergonomics by eliminating the need for error handling.

My biggest takeaway moving forward is that if I have the urge to set something to 0 or -1 until the real value arrives, there’s probably a better way to handle the situation. Wrapping types in Option is a relatively quick fix that buys most of the correctness, but it adds friction that can feel unnecessary, especially if the values are only ever None for a short time. The deeper structural fix is to rearrange the program’s use of the type system such that the values aren’t instantiated at all when they would have been placeholders or None, and idioms like the typestate pattern allow operations to be both correct and infallible.


Connect with me: GitHub・LinkedIn・RSS・(requires JavaScript)

  1. It really uses =<, not <=. ↩

  2. One approach would be to panic upon reaching any state that should be impossible, but with any practical level of test coverage, a refactor could make the panic reachable in some untested corner case. Even without refactoring, panicking is a human-assured “trust me” construct rather than machine-proven correctness. Using the type system to ensure that theoretically impossible states are actually impossible in the program is more robust. ↩

  3. In the codebase, Established is wrapped in SyncedState<T>, which defines logic shared with other synchronized TCP states. This detail is omitted here for simplicity. ↩

  4. The compiler error (at the time of writing) suggests using ref to avoid moving the value, but that version also fails to compile. Regardless, the key point is that the SynReceived and Established structs are neither Clone nor Copy and transition methods consume self. ↩