Proposal for 'indirect' modifier keyword for struct properties

IndirectProposal.md

Proposal for indirect modifier for struct properties

• Proposal: SE-NNNN
• Authors: Eneko Alonso
• Review Manager: TBD
• Status: Awaiting implementation

Introduction

Add support for indirect modifier keyword for struct properties

Swift-evolution thread: Pitch: Using indirect modifier for struct properties

Motivation

It is a known limitation that structs, being value types, cannot contain properties of the same type. For example, the following code is invalid:

struct Foo {
  var foo: Foo // Error: Value type 'Foo' cannot have a stored property that recursively contains it
}

This code is invalid because in order to create an instance of Foo, we would have to provide an infinite amount of instances. Instantiating it would require infinite memory.

Furthermore, the following code is also invalid:

struct List<T> {
  var value: T
  var next: List<T>? // Error: Value type 'List<T>' cannot have a stored property that recursively contains it
}

While a nil value should be enough to break infinite recursion, this code is invalid because Optional was consciously implemented to not support recursion in favor of yielding higher performance. In Joe Groff's words:

By not marking Optional or its cases indirect, we explicitly made the choice not to support recursion using Optional because we considered performance to be more important. Who benefits from the indirect keyword?

Proposed solution

This proposal would like to allow using indirect modifier on struct properties, like this:

struct List<T> {
  var value: T
  indirect var next: List<T>?
}

Detailed design

TBD

Source compatibility

Purely additive change, would not affect any existing code.

Effect on ABI stability

TBD

Effect on API resilience

TBD

Alternatives considered

There are several ways recursion can be achieved for struct, as seen below.

Using a property wrapper

Class-based property wrappers make it possible for structs to "store" properties in the heap, emulating indirection.

• Pros: property wrappers are cool
• Cons: immutable structs can be modified 😅

@propertyWrapper
class Indirect<Value> {
    var value: Value

    init(wrappedValue initialValue: Value) {
        value = initialValue
    }

    var wrappedValue: Value {
        get { value }
        set { value = newValue }
    }
}

struct List<T> {
    var value: T
    @Indirect var next: List?  // Recursion 🎉
}

// Usage
let integers = List(value: 1)
integers.next = List(value: 2) // Observe we are modifying an immutable struct (`let`)
print(integers.next?.value) // Optional(2)

Using a Box

Using a Box, we can introduce indirection to a value stored in the heap. This allows for recursion.

• Pros: immutable struct cannot be updated
• Cons: accessign the boxed value requires going through .content

class Box<T> {
    var content: T

    init(_ content: T) {
        self.content = content
    }
}

struct List<T> {
    var value: T
    var next: Box<List<T>>?  // Recursion 🎉
}

var integers = List(value: 1)
integers.next = Box(List(value: 2)) // `var` is required to make changes
print(integers.next?.content.value) // Optional(2)

Using a custom Optional type

Optional does not support indirection for performance reasons, as stated above. However, we can define our own optional enum type like this:

• Pros: uses enum indirection
• Cons: accessign the associated value requires if case, switch, or a computed property (eg. .content)

indirect enum IndirectOptional<T> {
    case none
    case some(T)

    var content: T? {
        if case let .some(content) = self {
            return content
        }
        return nil
    }
}

struct List<T> {
    var value: T
    var next: IndirectOptional<List<T>> = .none // Recursion 🎉
}
var integers = List(value: 1)
integers.next = .some(List(value: 2))
print(integers.next.content?.value) // Optional(2)

Using classes instead of struct

Users can write classes, instead of structs, to handle scenarios where recursion is needed (linked lists, binary trees, etc).

class List<T> {
    var value: T
    var next: List<T>?  // Recursion 🎉

    init(value: T) {
        self.value = value
    }
}

let integers = List(value: 1)
integers.next = List(value: 2)
print(integers.next?.value) // Optional(2)