CODEWITHSUNDEEP
swiftrecursionenumsinfinite-looprecursive-datastructures
exists-forall
exists-forall

Reputation: 4258

Swift recursive enum enters infinite loop in constructor

I've created a recursive enum in Swift that compiles without errors or warnings, but which enters an infinite loop when I try to instantiate it:

enum Tree<T> {
    case Leaf(T)
    case Branch(T, [Tree<T>])
}

Tree.Leaf(0) // enters infinite loop
Tree.Branch(0, []) // enters infinite loop

The infinite loop occurs upon instantiation, not upon printing or any other use of the instance. Even if nothing is ever done with the result, Tree.Leaf(0) still runs forever. Just to be clear: the infinite loop occurs at runtime, not compile time, but occurs immediately upon instantiation.

Strangely, the following very similar data structure works perfectly:

enum WorkingTree<T> {
    case Leaf(T)
    case Branch([WorkingTree<T>]) // notice the lack of a `T` in this case
}

WorkingTree.Leaf(0) // works fine
WorkingTree.Branch([.Leaf(1), .Leaf(2)]) // works fine

Perhaps even more strangely the following data structure also works perfectly:

enum ConcreteTree {
    case Leaf(Int)
    case Branch(Int, [ConcreteTree])
}

ConcreteTree.Leaf(0) // works fine
ConcreteTree.Branch(0, []) // works fine

Why is my original data structure entering an infinite loop when I try to instantiate it, while these other almost identical data structures are not?

EDIT:

In the Swift REPL, the problem seems to be dependent on whether or not the instantiation occurs in the same "block" as the type declaration. If I type the following into the Swift REPL:

1> enum Tree<T> {
2.     case Leaf(T)
3.     case Branch(T, [Tree<T>])
4. } // press enter, declare type
5> Tree.Leaf(0) // separate command to the REPL

then it fails with an infinite loop. However if I enter them as part of the same statement:

1> enum Tree<T> {
2.     case Leaf(T)
3.     case Branch(T, [Tree<T>])
4. } // press down arrow, continue multiline command
5. Tree.Leaf(0) // part of the same command

Then it does not enter an infinite loop, and works as expected.

What could be going on?

EDIT 2:

Things have gotten even stranger. The following code compiles and runs, but enters an infinite loop at a very unexpected point:

enum Tree<T> {
    case Leaf(T)
    case Branch(T, [Tree<T>])
}

let test = Tree.Leaf(0)
print("Milestone 1") // prints

switch test {
    case .Leaf(_): print("Milestone 2") // prints
    default: print("This should never be called")
}

func no_op<T>(x: T) {}

no_op(test) // infinite loop entered here
print("Milestone 3") // DOES NOT print

no_op(Tree.Leaf(0))
print("Milestone 4") // DOES NOT print

what could possibly be deferring the infinite loop until that no_op call?

Upvotes: 5

Views: 195

Answers (1)

matt
matt

Reputation: 535880

You forgot to say indirect:

enum Tree<T> {
    indirect case Leaf(T)
    indirect case Branch(T, [Tree<T>])
}

I'm a little surprised that the code compiled without it; I'd suggest filing a bug report.

Upvotes: 5

Related Questions