Recursive Shapes

Note: Throughout this document, the word "box" always refers to a Rust Box<T>, a heap allocated pointer to T, and not the Smithy concept of boxed vs. unboxed.

Recursive shapes pose a problem for Rust, because the following Rust code will not compile:

#![allow(unused)]
fn main() {
struct TopStructure {
    intermediate: IntermediateStructure
}

struct IntermediateStructure {
    top: Option<TopStructure>
}
}

  |
3 | struct TopStructure {
  | ^^^^^^^^^^^^^^^^^^^ recursive type has infinite size
4 |     intermediate: IntermediateStructure
  |     ----------------------------------- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `main::TopStructure` representable

This occurs because Rust types must be a size known at compile time. The way around this, as the message suggests, is to Box the offending type. smithy-rs implements this design in RecursiveShapeBoxer.kt

To support this, as the message suggests, we must "Box" the offending type. There is a touch of trickiness—only one element in the cycle needs to be boxed, but we need to select it deterministically such that we always pick the same element between multiple codegen runs. To do this the Rust SDK will:

Topologically sort the graph of shapes.
Identify cycles that do not pass through an existing Box, List, Set, or Map
For each cycle, select the earliest shape alphabetically & mark it as Box in the Smithy model by attaching the custom RustBoxTrait to the member.
Go back to step 1.

This would produce valid Rust:

#![allow(unused)]
fn main() {
struct TopStructure {
    intermediate: IntermediateStructure
}

struct IntermediateStructure {
    top: Box<Option<TopStructure>>
}
}

Backwards Compatibility Note!

Box is not generally compatible with T in Rust. There are several unlikely but valid model changes that will cause the SDK to produce code that may break customers. If these are problematic, all are avoidable with customizations.

A recursive link is added to an existing structure. This causes a member that was not boxed before to become Box.

Workaround: Mark the new member as Box in a customization.
A field is removed from a structure that removes the recursive dependency. The SDK would generate T instead of Box.

Workaround: Mark the member that used to be boxed as Box in a customization. The Box will be unnecessary, but we will keep it for backwards compatibility.

Smithy Rust

Recursive Shapes