780 Advanced

780-const-generic-struct — Const Generic Struct

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "780-const-generic-struct — Const Generic Struct" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Ring buffers (circular buffers) are fundamental data structures in operating systems, audio processing, and producer-consumer patterns. Key difference from OCaml: 1. **Type

Tutorial

The Problem

Ring buffers (circular buffers) are fundamental data structures in operating systems, audio processing, and producer-consumer patterns. A fixed-capacity ring buffer avoids heap allocation and provides O(1) push and pop with power-of-two sizes enabling fast modulo via bitmask. Using a const generic capacity RingBuffer<T, CAP> embeds the capacity in the type, enabling different capacities to be different types with no runtime dispatch.

🎯 Learning Outcomes

• Implement RingBuffer<T: Copy, const CAP: usize> with head, tail, and len tracking

• Write push(item) -> Result<(), T> (returns item on overflow) and pop() -> Option<T>

• Use modulo arithmetic to wrap head and tail indices: (self.tail + 1) % CAP

• Implement peek(), is_empty(), is_full(), and iter() for a complete API

• Verify that RingBuffer<u32, 8> is exactly (8 * 4 + overhead) bytes with no heap pointer

Code Example

pub struct RingBuffer<T, const CAP: usize> {
    data: [Option<T>; CAP],
    head: usize,
    tail: usize,
}

let rb: RingBuffer<i32, 16> = RingBuffer::new();

(* No compile-time capacity - runtime parameter *)
type 'a ring_buffer = {
  data: 'a option array;
  mutable head: int;
  mutable tail: int;
}

let create cap = {
  data = Array.make cap None;
  head = 0;
  tail = 0;
}

Key Differences

Type-level capacity: Rust's RingBuffer<u32, 8> and RingBuffer<u32, 16> are different types; OCaml's equivalent would be the same int array ref record type at different sizes.

Stack allocation: Rust's small ring buffers can live on the stack; OCaml arrays are always heap-allocated.

Option overhead: [Option<T>; CAP] uses one byte per slot for the discriminant; a production implementation uses MaybeUninit<T> to avoid this.

Power-of-two optimization: Rust can specialize for power-of-two CAP using & (CAP - 1) instead of % CAP; this is a zero-cost const-generic specialization.

OCaml Approach

OCaml's Queue.t is a standard doubly-linked-list queue — heap-allocated, no fixed capacity. For fixed-capacity ring buffers, OCaml uses Array.make cap None with mutable head, tail, and len references. Libraries like Faraday use ring buffers internally for I/O buffering. OCaml's Bigarray provides C-allocated ring buffers for zero-copy I/O in capnp-rpc and mirage.

Full Source

#![allow(clippy::all)]
//! # Const Generic Struct
//!
//! Structures parameterized by compile-time constants.

/// Fixed-capacity ring buffer
#[derive(Debug)]
pub struct RingBuffer<T, const CAP: usize> {
    data: [Option<T>; CAP],
    head: usize,
    tail: usize,
    len: usize,
}

impl<T: Copy, const CAP: usize> RingBuffer<T, CAP> {
    pub fn new() -> Self {
        RingBuffer {
            data: [None; CAP],
            head: 0,
            tail: 0,
            len: 0,
        }
    }

    pub const fn capacity(&self) -> usize {
        CAP
    }

    pub const fn len(&self) -> usize {
        self.len
    }

    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub const fn is_full(&self) -> bool {
        self.len == CAP
    }

    pub fn push(&mut self, item: T) -> Result<(), T> {
        if self.is_full() {
            return Err(item);
        }
        self.data[self.tail] = Some(item);
        self.tail = (self.tail + 1) % CAP;
        self.len += 1;
        Ok(())
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.is_empty() {
            return None;
        }
        let item = self.data[self.head].take();
        self.head = (self.head + 1) % CAP;
        self.len -= 1;
        item
    }

    pub fn peek(&self) -> Option<&T> {
        if self.is_empty() {
            None
        } else {
            self.data[self.head].as_ref()
        }
    }
}

impl<T: Copy, const CAP: usize> Default for RingBuffer<T, CAP> {
    fn default() -> Self {
        Self::new()
    }
}

/// Bit set with compile-time size (stored as array of u64 words)
/// The number of u64 words is passed as a const generic WORDS parameter.
#[derive(Debug, Clone, Copy)]
pub struct BitSet<const BITS: usize, const WORDS: usize> {
    data: [u64; WORDS],
}

impl<const BITS: usize, const WORDS: usize> BitSet<BITS, WORDS> {
    pub fn new() -> Self {
        BitSet { data: [0; WORDS] }
    }

    pub const fn bits(&self) -> usize {
        BITS
    }

    pub fn set(&mut self, idx: usize) {
        if idx < BITS {
            self.data[idx / 64] |= 1 << (idx % 64);
        }
    }

    pub fn clear(&mut self, idx: usize) {
        if idx < BITS {
            self.data[idx / 64] &= !(1 << (idx % 64));
        }
    }

    pub fn get(&self, idx: usize) -> bool {
        if idx < BITS {
            (self.data[idx / 64] >> (idx % 64)) & 1 != 0
        } else {
            false
        }
    }

    pub fn count_ones(&self) -> usize {
        self.data.iter().map(|&x| x.count_ones() as usize).sum()
    }
}

impl<const BITS: usize, const WORDS: usize> Default for BitSet<BITS, WORDS> {
    fn default() -> Self {
        Self::new()
    }
}

/// Fixed-size string
#[derive(Debug, Clone, Copy)]
pub struct FixedString<const N: usize> {
    data: [u8; N],
    len: usize,
}

impl<const N: usize> FixedString<N> {
    pub const fn new() -> Self {
        FixedString {
            data: [0; N],
            len: 0,
        }
    }

    pub const fn capacity(&self) -> usize {
        N
    }

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

    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn as_str(&self) -> &str {
        std::str::from_utf8(&self.data[..self.len]).unwrap_or("")
    }

    pub fn push_str(&mut self, s: &str) -> bool {
        let bytes = s.as_bytes();
        if self.len + bytes.len() <= N {
            self.data[self.len..self.len + bytes.len()].copy_from_slice(bytes);
            self.len += bytes.len();
            true
        } else {
            false
        }
    }
}

impl<const N: usize> Default for FixedString<N> {
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_ring_buffer() {
        let mut rb: RingBuffer<i32, 4> = RingBuffer::new();
        assert_eq!(rb.capacity(), 4);

        rb.push(1).unwrap();
        rb.push(2).unwrap();
        assert_eq!(rb.pop(), Some(1));
        assert_eq!(rb.pop(), Some(2));
    }

    #[test]
    fn test_ring_buffer_wrap() {
        let mut rb: RingBuffer<i32, 3> = RingBuffer::new();
        rb.push(1).unwrap();
        rb.push(2).unwrap();
        rb.push(3).unwrap();
        assert!(rb.push(4).is_err()); // Full

        assert_eq!(rb.pop(), Some(1));
        rb.push(4).unwrap(); // Now there's room
        assert_eq!(rb.pop(), Some(2));
    }

    #[test]
    fn test_bitset() {
        // BitSet<100, 2> means 100 bits stored in 2 u64 words (128 bits capacity)
        let mut bs: BitSet<100, 2> = BitSet::new();
        assert_eq!(bs.bits(), 100);

        bs.set(0);
        bs.set(50);
        bs.set(99);

        assert!(bs.get(0));
        assert!(bs.get(50));
        assert!(bs.get(99));
        assert!(!bs.get(1));
        assert_eq!(bs.count_ones(), 3);
    }

    #[test]
    fn test_fixed_string() {
        let mut s: FixedString<16> = FixedString::new();
        assert!(s.push_str("hello"));
        assert_eq!(s.as_str(), "hello");
        assert!(s.push_str(" world"));
        assert_eq!(s.as_str(), "hello world");
    }
}

(* Generic structs parameterised by const in OCaml — using functors *)

module type DIMS = sig val rows : int val cols : int end

module Matrix (D : DIMS) = struct
  type t = { data: float array array }

  let create () =
    { data = Array.init D.rows (fun _ -> Array.make D.cols 0.0) }

  let get m r c = m.data.(r).(c)
  let set m r c v = m.data.(r).(c) <- v

  let rows = D.rows
  let cols = D.cols

  let identity () =
    assert (D.rows = D.cols);
    let m = create () in
    for i = 0 to D.rows - 1 do set m i i 1.0 done;
    m

  let print m =
    for r = 0 to D.rows - 1 do
      for c = 0 to D.cols - 1 do
        Printf.printf " %6.2f" (get m r c)
      done;
      print_newline ()
    done
end

(* Multiply M1(R×N) × M2(N×C) → M3(R×C) *)
module MatMul (R : sig val n : int end)
              (N : sig val n : int end)
              (C : sig val n : int end) = struct
  module MA = Matrix(struct let rows = R.n let cols = N.n end)
  module MB = Matrix(struct let rows = N.n let cols = C.n end)
  module MC = Matrix(struct let rows = R.n let cols = C.n end)

  let multiply a b =
    let c = MC.create () in
    for r = 0 to R.n - 1 do
      for col = 0 to C.n - 1 do
        let s = ref 0.0 in
        for k = 0 to N.n - 1 do
          s := !s +. MA.get a r k *. MB.get b k col
        done;
        MC.set c r col !s
      done
    done;
    c
end

module D2 = struct let n = 2 end
module D3 = struct let n = 3 end

module M2x3 = Matrix(struct let rows = 2 let cols = 3 end)
module M3x2 = Matrix(struct let rows = 3 let cols = 2 end)
module Mul23 = MatMul(D2)(D3)(D2)

let () =
  let a = M2x3.create () in
  M2x3.set a 0 0 1.0; M2x3.set a 0 1 2.0; M2x3.set a 0 2 3.0;
  M2x3.set a 1 0 4.0; M2x3.set a 1 1 5.0; M2x3.set a 1 2 6.0;
  Printf.printf "A (2×3):\n"; M2x3.print a

✓ Tests Rust test suite

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_ring_buffer() {
        let mut rb: RingBuffer<i32, 4> = RingBuffer::new();
        assert_eq!(rb.capacity(), 4);

        rb.push(1).unwrap();
        rb.push(2).unwrap();
        assert_eq!(rb.pop(), Some(1));
        assert_eq!(rb.pop(), Some(2));
    }

    #[test]
    fn test_ring_buffer_wrap() {
        let mut rb: RingBuffer<i32, 3> = RingBuffer::new();
        rb.push(1).unwrap();
        rb.push(2).unwrap();
        rb.push(3).unwrap();
        assert!(rb.push(4).is_err()); // Full

        assert_eq!(rb.pop(), Some(1));
        rb.push(4).unwrap(); // Now there's room
        assert_eq!(rb.pop(), Some(2));
    }

    #[test]
    fn test_bitset() {
        // BitSet<100, 2> means 100 bits stored in 2 u64 words (128 bits capacity)
        let mut bs: BitSet<100, 2> = BitSet::new();
        assert_eq!(bs.bits(), 100);

        bs.set(0);
        bs.set(50);
        bs.set(99);

        assert!(bs.get(0));
        assert!(bs.get(50));
        assert!(bs.get(99));
        assert!(!bs.get(1));
        assert_eq!(bs.count_ones(), 3);
    }

    #[test]
    fn test_fixed_string() {
        let mut s: FixedString<16> = FixedString::new();
        assert!(s.push_str("hello"));
        assert_eq!(s.as_str(), "hello");
        assert!(s.push_str(" world"));
        assert_eq!(s.as_str(), "hello world");
    }
}

Deep Comparison

OCaml vs Rust: Const Generic Struct

Ring Buffer with Const Capacity

Rust

pub struct RingBuffer<T, const CAP: usize> {
    data: [Option<T>; CAP],
    head: usize,
    tail: usize,
}

let rb: RingBuffer<i32, 16> = RingBuffer::new();

OCaml

(* No compile-time capacity - runtime parameter *)
type 'a ring_buffer = {
  data: 'a option array;
  mutable head: int;
  mutable tail: int;
}

let create cap = {
  data = Array.make cap None;
  head = 0;
  tail = 0;
}

BitSet with Const Size

Rust

pub struct BitSet<const BITS: usize>
where
    [(); (BITS + 63) / 64]: Sized,
{
    data: [u64; (BITS + 63) / 64],
}

let bs: BitSet<100> = BitSet::new(); // Exactly 2 u64s

Key Differences

Aspect	OCaml	Rust
Capacity param	Runtime	Compile-time
Memory layout	Heap array	Stack-allocated
Size known	Runtime	Compile-time
Type safety	Same type any size	Different types

Exercises

Optimize for power-of-two capacity: replace % CAP with & (CAP - 1) and add a const_assert!(CAP.is_power_of_two()) in new().

Replace [Option<T>; CAP] with [MaybeUninit<T>; CAP] to eliminate the Option discriminant overhead — add a safety comment explaining the invariant.

Add an Iterator implementation for RingBuffer that reads elements from head to tail without modifying the buffer.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust