#set document(title: "2.10 Self-referential structs", author: "Modular Inc. / XYZ Homework") #set page(width: 8.5in, height: auto, margin: 1in) #import "@preview/cetz:0.5.2" #set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en") #show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math")) #set par(justify: true, leading: 0.62em, spacing: 0.9em) #set enum(spacing: 1.1em) // room between list items so tall inline fractions don't collide #set list(spacing: 1.1em) #set table(stroke: 0.5pt + rgb("#c7ccd3")) #let BLUE = rgb("#183B6F") // brand navy — section bars + example/solution labels (white on navy 11.09:1) #let ORANGE = rgb("#A94509") // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text) #let RED = rgb("#DC2626") // brand error-600 #let GREEN = rgb("#059669") // brand success-600 (decoration only; small green text uses green-text #007942) #show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt, fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt, text(fill: white, weight: "bold", size: 19pt, it.body)) #show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt, fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt, text(fill: white, weight: "bold", size: 12pt, it.body)) #show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body) #show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body) #let examplebox(label, title, body) = block(width: 100%, breakable: true, fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt, above: 12pt, below: 12pt)[ #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt, text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]] #body] // rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade #let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint, stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt), above: 11pt, below: 11pt)[ #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)] #linebreak() #body] #let solutionbox(body) = block(above: 4pt, below: 8pt)[ #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body] #let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"), stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[ #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))] // Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a // consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the // print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a // degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero. #let _STD_W = 3.5 #let _WIDE_W = 5.6 #let _MAX_H = 3.4 #let _ASPECT_WIDE = 2.2 #let _UPSCALE_MAX = 1.15 #let stdfig(body) = context { let m = measure(body) let w = calc.max(m.width / 1in, 0.01) let h = calc.max(m.height / 1in, 0.01) let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W } let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX) align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body))) } #show figure: set block(breakable: false) #set figure(gap: 8pt) #show figure.caption: set text(size: 8.5pt, fill: rgb("#555")) == 2.10#h(0.6em)Self-referential structs Some data structures don't fit well with value semantics. Lists, trees, and graphs all need nodes that point to each other. You can't build these by nesting one value inside another, because the type would keep growing forever. In Mojo, you build these shapes with pointers, heap allocation, and manual cleanup. The idea may feel new at first, but the pattern stays simple once you see it in small steps. === Avoid direct self-reference Mojo won't let you build a type that stores another instance of itself, even when nested within an Optional: struct Node: var value: String var next: Optional\[Node\] \# ERROR: Recursive reference \# ... Each struct has a fixed layout. If Node held another Node directly, the compiler wouldn't know how much space to reserve. Optional fields don't help, because the outer value still needs room for the inner one. Pointers solve this problem. Pointers have a fixed size, and they let values point at each other without blowing up the type. === Adding self-referential pointers The following code shows how to set up a node that can point to its own type. This sample gives you a node type with a value slot and a single link to the next node: struct Node\[ElementType: ImplicitlyCopyable & Writable\](Movable): comptime NodePointer = UnsafePointer\[Self, MutUntrackedOrigin\] var value: Optional\[Self.ElementType\] \# The \`Node\`'s value var next: Optional\[Self.NodePointer\] \# Pointer to the next \`Node\` \# Uses an \`Optional\` value to allow 'empty' Node construction \# that can be moved into newly allocated memory def \_\_init\_\_(out self, value: Optional\[Self.ElementType\] = None): self.value = value self.next = {} The code defines a type-specific NodePointer type alias built on #link("https://mojolang.org/docs/std/memory/unsafe_pointer/UnsafePointer/")[UnsafePointer]. MutUntrackedOrigin lets the pointer represent dynamically-allocated memory that won't be tracked by the lifetime checker. You'll need to both allocate and deallocate memory as needed. The next field is an Optional\[Self.NodePointer\] because a node may or may not link to another node. UnsafePointer is non-nullable, so Optional provides the null state. Optional\[UnsafePointer\] has the same memory layout as a raw pointer, so there's no overhead. For more on this pattern, see Working with nullability. The optional value lets you create "empty" nodes, enabling you to move new Node memory allocations into place. === Building nodes Here's the key pattern you'll use in many reference structures: + Allocate space. + Construct a value-holding node. + Move it into the allocated memory. + Return the pointer. And here's an example of that pattern: \@staticmethod def make\_node(value: Self.ElementType) -\> Self.NodePointer: var node\_ptr = alloc\[Self\](1) node\_ptr.init\_pointee\_move(Self(value)) return node\_ptr This "allocate space, initialize, and move" approach creates safe pointer-based structures in Mojo. === Linking nodes To link nodes, create a new node and set your next pointer to point at it. This example shows how to append a new node using a supplied value. If a next node already exists, the code frees it before appending the new node. def append(mut self, value: Self.ElementType): \# Free chain if replacing \`next\` if self.next: var next\_ptr = self.next.value() next\_ptr\[\].free\_chain() next\_ptr.destroy\_pointee() next\_ptr.free() self.next = Self.make\_node(value) === Walking the list To walk the list, follow the chain until you reach the end. Recursive code makes this easy to read. This example prints the value stored at each node: \@staticmethod def print\_list(node: Optional\[Self.NodePointer\]): if not node: print("Empty list") return var node\_ptr = node.value() current\_value: Optional\[Self.ElementType\] = node\_ptr\[\].value if current\_value: print(current\_value.value(), end=" ") if node\_ptr\[\].next: Self.print\_list(node\_ptr\[\].next) else: print() The pattern is simple: check the value, print it if it exists, then move to the next link. #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ This example uses a static method, but you can also implement it as an instance method. ] === Cleaning up Because you allocate each node yourself, you're also responsible for freeing it. This cleanup walks the chain and frees each node after destroying its pointee: def free\_chain(self): var current = self.next while current: var current\_ptr = current.value() next\_node = current\_ptr\[\].next current\_ptr.destroy\_pointee() current\_ptr.free() current = next\_node The "head" node stays allocated unless you explicitly free it yourself: list\_head\[\].free\_chain() list\_head.destroy\_pointee() list\_head.free() ==== Destructors When you build real Mojo data structures, you usually want a safe API that hides raw pointers from users. In a complete linked-list type (rather than a small demo of linkable nodes) the parent list handles node allocation and freeing. Because it owns the nodes, it also performs cleanup in its destructor. Here's a small example that shows how to deinitialize self: struct LinkedList\[T\]: var \_head: Optional\[Self.\_NodePointer\] def \_\_del\_\_(deinit self): """Clean up the list by freeing all nodes. Notes: Time complexity: O(n) in len(self). See Also: "Choose the form of the Destructor!" -- Gozer, "Ghostbusters" (1984). """ var curr = self.\_head while curr: var next = curr.value()\[\].next curr.value().destroy\_pointee() curr.value().free() curr = next #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[Putting it together] #notebox("Note", rgb("#8a94a6"), rgb("#556666"), rgb("#f7f8fa"))[ #emph[View full sample code] from std.os import abort comptime Element = String \# Adapt for your type comptime ListNode = Node\[Element\] \# Constructing a LinkedList struct Node\[ElementType: ImplicitlyCopyable & Writable\](Movable): comptime NodePointer = UnsafePointer\[Self, MutUntrackedOrigin\] var value: Optional\[Self.ElementType\] \# The \`Node\`'s value var next: Optional\[Self.NodePointer\] \# Pointer to the next \`Node\` \# Uses an \`Optional\` value to allow 'empty' Node construction \# that can be moved into newly allocated memory def \_\_init\_\_(out self, value: Optional\[Self.ElementType\] = None): self.value = value self.next = {} \# Constructs a \`Node\` with a \`value\` with heap allocation and \# returns a pointer to the new \`Node\`. \@staticmethod def make\_node(value: Self.ElementType) -\> Self.NodePointer: var node\_ptr = alloc\[Self\](1) node\_ptr.init\_pointee\_move(Self(value)) return node\_ptr \# Constructs a \`Node\` with allocated memory, assigns a value, appends \# the pointer to \`self.next\`. Replaces any existing \`next\`. def append(mut self, value: Self.ElementType): \# Free chain if replacing \`next\` if self.next: var next\_ptr = self.next.value() next\_ptr\[\].free\_chain() next\_ptr.destroy\_pointee() next\_ptr.free() self.next = Self.make\_node(value) \# Prints the list starting at this pointer's pointee \@staticmethod def print\_list(node: Optional\[Self.NodePointer\]): if not node: print("Empty list") return var node\_ptr = node.value() current\_value: Optional\[Self.ElementType\] = node\_ptr\[\].value if current\_value: print(current\_value.value(), end=" ") if node\_ptr\[\].next: Self.print\_list(node\_ptr\[\].next) else: print() \# Releases all successively allocated \`Node\` pointees. Does not release self def free\_chain(self): var current = self.next while current: var current\_ptr = current.value() next\_node = current\_ptr\[\].next current\_ptr.destroy\_pointee() current\_ptr.free() current = next\_node def main(): var values: List\[Element\] = \["one", "one", "two", "three", "five", "eight"\] var list\_head = ListNode.make\_node(values\[0\]) var current = list\_head for idx in range(1, len(values), 1): current\[\].append(values\[idx\]) current = current\[\].next.value() ListNode.print\_list(list\_head) \# Demonstrates cleanup. In short-lived programs, the OS reclaims memory \# at exit list\_head\[\].free\_chain() list\_head.destroy\_pointee() list\_head.free() one one two three five eight Output: ] ] === What next? - Learn more about #strong[pointers and memory safety] in Mojo's #link("https://mojolang.org/docs/std/memory/unsafe_pointer/UnsafePointer/")[UnsafePointer] and lifetime and origin rules guides. - Learn more about how to #strong[manage cleanup] in the Mojo destructor documentation. - Learn more about generic structures with traits and how they let you build #strong[reusable node and list types].