Learn Rust With Entirely Too Many Linked Lists
← Ch V
Chapter VI A Production Unsafe Deque
Ch VII →
  1. 37 — Layout
  2. 38 — Variance and Subtyping
  3. 39 — Basics
  4. 40 — Panic Safety
  5. 41 — Boring Combinatorics
  6. 42 — Filling In Random Bits
  7. 43 — Testing
  8. 44 — Send, Sync, and Compile Tests
  9. 45 — An Introduction To Cursors
  10. 46 — Implementing Cursors
  11. 47 — Testing Cursors
  12. 48 — Final Code
44

Send, Sync, and Compile Tests

Send and Sync are auto-traits — the compiler implements them for any type whose fields all implement them. Raw pointers do not implement either, on the assumption that an unsafe author hasn't proved thread-safety. We have to opt our list back in by writing the impls ourselves, with unsafe impl. Then we add compile-fail tests to verify we got the bounds right.

  1. The opt-in impls. A LinkedList<T> is Send exactly when T: Send (moving the list to another thread moves all the elements). It's Sync when T: Sync (sharing &LinkedList<T> only exposes &T). Same impls again for Iter/IterMut/IntoIter.
    unsafe impl<T: Send> Send for LinkedList<T> {}
unsafe impl<T: Sync> Sync for LinkedList<T> {}

unsafe impl<T: Send> Send for Iter<'_, T> {}
unsafe impl<T: Sync> Sync for Iter<'_, T> {}
unsafe impl<T: Send> Send for IterMut<'_, T> {}
unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
unsafe impl<T: Send> Send for IntoIter<T> {}
unsafe impl<T: Sync> Sync for IntoIter<T> {}
  2. Verify the bounds with a static-assertion trick: a function with a where-clause that only compiles if the impl exists. Place these in tests; they're compile-time checks, no runtime cost. Symmetrically, set up a trybuild test that pins the negative cases (e.g., LinkedList<Rc<i32>> is not Send).
    #[cfg(test)]
fn _assert_send_sync() {
    fn assert_send<T: Send>() {}
    fn assert_sync<T: Sync>() {}
    assert_send::<LinkedList<i32>>();
    assert_sync::<LinkedList<i32>>();
    assert_send::<Iter<'_, i32>>();
    assert_send::<IterMut<'_, i32>>();
    assert_send::<IntoIter<i32>>();
}

// trybuild test (in tests/compile-fail/not-send.rs):
// fn must_be_send<T: Send>() {}
// fn main() {
//     must_be_send::<LinkedList<std::rc::Rc<i32>>>();
//     // expected: error[E0277]: ... cannot be sent between threads safely
// }
  3. Variance has the same compile-test pattern. A function that takes LinkedList<&'static T> and returns it as LinkedList<&'a T> only compiles if the type is covariant. Add it to the test suite as a regression guard — change the marker to PhantomData<*mut Node<T>> and this assertion stops compiling.
    #[cfg(test)]
fn _assert_covariant<'a, T>(
    long: LinkedList<&'static T>,
) -> LinkedList<&'a T> {
    long  // only compiles if LinkedList is covariant in T
}