Who benefits from the `indirect` keyword?

Good morning, Felicias,

I was thinking - what is the benefit of having an indirect keyword for enum cases? Apple's The Swift Programming Language says:

You indicate that an enumeration case is recursive by writing indirect before it, which tells the compiler to insert the necessary layer of indirection.

Does it have any benefit for a programmer to know that? Is there some risk of infinite loop or another danger? How are we telling compiler this, if compiler is able to know on its own if we forget to add the indirect keyword? That looks like it could be working just like it does now without this keyword.

2 Likes

Enums in Swift are really memory efficient(comparing to smth like java) while being remarkably powerful(one of the main Swift's selling point for me).
The problem with indirect cases is enum's memory layout. Having an indirect case in enum makes it's memory layout not trivial so it is representation becomes more complicated(correct me if I'm wrong).

Do you mean that the keyword has been introduced to remind programmers about the performance cost?

Yes, as we really don't need using try before each throwing function, we really don't need placing indirect before indirect enum rather than showing that this enum is not as simple as the other ones.

Here Is what I found on the forum:

2 Likes

Well the most common use case for indirect would be to allow for recursive enums I guess.

enum BinaryTree<T> {
   case empty
   indirect case node(left: BinaryTree, value: T, right: BinaryTree)
}

What is the allocation size for this enum type? You can't say without making the node case indirect (so only storing a reference).
I am pretty sure the compiler could infer the keyword (like possibly many other keywords by analyzing the code) but some of that analysis would be very time-consuming and non-trivial in many ways.

I didn't know about the "rare case" usecase. That's an interesting idea.

2 Likes

So are there times when the compiler doesn’t throw an error about missing indirect? There should be, to make the point about avoiding heavy compilation valid. Otherwise, if compiler always knows about something, that would make a keyword redundant from this point of view. Possibly valid from other points.

The compiler does not always know when indirect is necessary or desired. For example, Optional<T> is compiled as part of the standard library, and we wouldn't want Optional to always be indirect, because that would mean every Int? or String? requires an additional allocation to hold the indirect value. Nonetheless, code in another module could attempt to instantiate Optional in a way that would require indirect-ness to handle recursion:

struct Recursive {
  var value: Int
  var next: Recursive?
}

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. You use indirect when you need recursion or want to favor data size over performance. These are judgments for which the compiler can't always make the right choice on its own, so it's up to the programmer to make them.

19 Likes


It doesn't work

Right. Making that work would require using an indirect enum instead of Optional. I used that as an example of how making enums automatically indirect when needed is non-trivial with generic enums, when the indirect-ness may depend on the structure of the generic arguments.

Hey @Joe_Groff :)

I've stumbled into this some time ago(SR-12755), and for work around I did something like

struct Recursive {
  var value: Int
  
  private var _next: [Recursive?] = [nil]
  var next: Recursive? {
    get { _next[0] }
    set { _next[0] = nil }
  }
}

which does works. But this should really work? What are the effects on type layout in this case and how the recursive optional of same type inside the array is handled?

Thanks in advance.

1 Like

The layout would be 1 Int + 1 Array. IIRC Array has its own heap-allocated storage under the hood (with a few metadata), so Recursive ends up having finite size (with the next entry floating somewhere else in the heap memory).

Also maybe like this?:

@propertyWrapper
enum Indirect<Value> {
  indirect case value(Value)

  init(wrappedValue: Value) { self = .value(wrappedValue) }

  var wrappedValue: Value {
    get { 
      guard case let .value(value) = self else { 
        fatalError("Unreachable")
      }
      return value
    }
    set { self = .value(newValue) }
  }
}

struct Recursive {
  @Indirect var next: Recursive?
}

Makes me thing we may want to have indirect inside struct, which would most definitely do different things compared to enum, but achieve the same effect on memory footprint.

7 Likes

That's kinda what I was expecting. Thank you @Lantua :)

Do you mean something like

struct Recursive {
  var value: Int
  indirect var next: Recursive?
}

?

I think this would make sense as you said.

1 Like

Supporting indirect on struct properties would be great, in my opinion, but the use cases are limited, and classes can be used to solve this.

I started writing a proposal last week, but didn't think it would be a noticeable improvement to the language. What do you think?

1 Like

Hi @eneko :)
I think that although it would be nice to have, I agree that it wouldn't add significant improvements to the language since as you mention the cases where we would need something like this would be very specific and limited. And also, it is easy to find another solution when we stumble in one of those cases
Also, as for the implementation of a feature like that, since involves type layout and additional allocation probably to hold the indirect value, I'm not sure if it is possible to add something like this at this moment because of that may affect ABI(this is more a question I really don't if that would be a factor in this case)
cc @Joe_Groff It would be possible to implement something like this?

Thanks @LucianoPAlmeida, I've opened a thread in Pitches: Using `indirect` modifier for `struct` properties

1 Like

No, compiler always knows about the memory layout of the certain concepts(enums, structs, classes etc.). You will have an error because the non-trivial layout makes the compiled code much more complicated than simple(trivial) enums` code.
To know more please read the thread I linked in the post.

As a workaround I can see these three options:

// Option 1
struct Recursive {
    var value: Int
    var next: UnsafePointer<Recursive>
}

// Option 2
indirect enum MyOptional<T> {
    case none
    case some(T)
}
struct Recursive {
    var value: Int
    var next: MyOptional<Recursive>
}

// Option 3
struct Recursive {
    var value: Int
    var next: [Recursive] // zero or one element
}

Option 1 would be probably the most painful to use memory management wise, option 3 is probably the least efficient (and allows for erroneous situations where array has more than one entry), option 2 is in between, I'd probably go with it. +1 for having indirect option on structs.

btw, why is it called "indirect"?

Recursive enum 'E' is not marked 'indirect'

Would make sense to mark Recursive enums recursive. Or if indirect is indeed meaningful we can use just that, and change the doc / and compiler diagnostics so it is actually:

Indirect enum 'E' is not marked 'indirect'

Only the designer could answer this. That said, recursive would be incorrect as you can mark any case as indirect so long as you deem it beneficial/necessary. Recursive cases are just the obvious necessary ones.

A slightly less obvious case is when you have a very large struct that you rarely use:

enum SomeEnum {
  case a, b
  indirect case c(LargeStruct)
}

Recall that the size of the enum is the size of the largest case (+discriminator). So if we don't use indirect, the size of SomeEnum would be about the size of LargeStruct. However, if the common cases are a and b, that would be very wasteful. So we add indirect to make the size of SomeEnum about the size of a pointer. When case c is used, the compiler will allocate a separate region for LargeStruct.

5 Likes