Protocol inheritance that heats up my computer

Question

Created Sep ’15

Replies 1

Boosts 0

Participants 1

I've noticed that a seemingly insignificant modification of the program below will make the compiler work for ever at 99% cpu.

This is the program without the modification (so it will compile normally):

protocol Nat {
    static var intValue: Int { get }
}
protocol NonZero : Nat {
    typealias Pred : Nat
}
struct Zero : Nat {
    static var intValue: Int { return 0 }
}
struct Succ<P: Nat> : NonZero {
    typealias Pred = P
    static var intValue: Int { return P.intValue + 1 }
}


protocol StaticArrayType {
    typealias Element
    typealias Arity : Nat
    var startIndex: Int { get }
    var endIndex: Int { get }
    subscript (position: Int) -> Element { get }
}

extension StaticArrayType {
    var startIndex: Int { return 0 }
    var endIndex: Int { return Arity.intValue }
}

struct EmptyStaticArray<Element> : StaticArrayType, CollectionType {
    typealias Arity = Zero
    subscript (position: Int) -> Element { fatalError("Index out of bounds!") }
}

struct StaticArray<Tail: StaticArrayType> : StaticArrayType, CollectionType {
    typealias Arity = Succ<Tail.Arity>
    var head: Tail.Element
    var tail: Tail
    subscript (position: Int) -> Tail.Element {
        return position == 0 ? head : tail[position - 1]
    }
}


infix operator ! { precedence 1 associativity right }
func !<T>(lhs: T, rhs: T) -> StaticArray<StaticArray<EmptyStaticArray<T>>> {
    return StaticArray(head: lhs, tail: StaticArray(head: rhs, tail: EmptyStaticArray<T>()))
}
func !<T, C where C: StaticArrayType, C.Element == T>(lhs: T, rhs: C) -> StaticArray<C> {
    return StaticArray(head: lhs, tail: rhs)
}


let a = 1 ! 2 ! 3 ! 4 ! 5 ! 6

for e in a { print(e) }

Now, if we let the StaticArrayType protocol inherit from CollectionType instead of declaring the CollectionType-conformance explicitly for both EmptyStaticArray and StaticArray, then the compiler will work (at 99% cpu) for ever.

If we reduce the number of elements in the static array a to 3 instead of 6, like this:

let a = 1 ! 2 ! 3

then both versions will compile in reasonable time, but the modified version will be slower.

Is this because of some known issue?

(Xcode 7)

EDIT: I filed 22772053 anyway, but I'm still interested to know more about this.

Boost

Answer 1

Jens OP

Sep ’15

Here's a similar but smaller example, this time I will show the code before the workaround is applied. This will make the compiler work at 100% cpu for a long time and eventually it will stop with an error msg saying that the expression is too complex to be solved in reasonable time:

protocol StaticArrayType : CollectionType {
    typealias Item
    var startIndex: Int { get }
    var endIndex: Int { get }
    subscript (position: Int) -> Item { get }
}
extension StaticArrayType {
    var startIndex: Int { return 0 }
}
struct EmptyStaticArray<Item> : StaticArrayType {
    var endIndex: Int { return 0 }
    subscript (position: Int) -> Item { fatalError("Index out of bounds.") }
}
struct StaticArray<Tail: StaticArrayType> : StaticArrayType {
    var head: Tail.Item
    var tail: Tail
    var endIndex: Int { return tail.endIndex + 1 }
    subscript (position: Int) -> Tail.Item {
        return position == 0 ? head : tail[position - 1]
    }
}
infix operator ! { precedence 1 associativity right }
func !<T>(lhs: T, rhs: T) -> StaticArray<StaticArray<EmptyStaticArray<T>>> {
    return StaticArray(head: lhs, tail: StaticArray(head: rhs, tail: EmptyStaticArray<T>()))
}
func !<T>(lhs: T.Item, rhs: T) -> StaticArray<T> {
    return StaticArray(head: lhs, tail: rhs)
}
let a = 1 ! 2 ! 3 ! 4 ! 5 ! 6 ! 7
for e in a { print(e) }

So, the workaround is the same as the one used in the code of the original post, namely to not let the StaticArray protocol inherit from CollectionType, but instead conform both concrete types to CollectionType, like this:

protocol StaticArrayType { // <-- NOTE: Workaround is to remove StaticArrayType's inheritance from CollectionType ...
    typealias Item
    var startIndex: Int { get }
    var endIndex: Int { get }
    subscript (position: Int) -> Item { get }
}
extension StaticArrayType {
    var startIndex: Int { return 0 }
}
struct EmptyStaticArray<Item> : StaticArrayType {
    var endIndex: Int { return 0 }
    subscript (position: Int) -> Item { fatalError("Index out of bounds.") }
}
struct StaticArray<Tail: StaticArrayType> : StaticArrayType {
    var head: Tail.Item
    var tail: Tail
    var endIndex: Int { return tail.endIndex + 1 }
    subscript (position: Int) -> Tail.Item {
        return position == 0 ? head : tail[position - 1]
    }
}
infix operator ! { precedence 1 associativity right }
func !<T>(lhs: T, rhs: T) -> StaticArray<StaticArray<EmptyStaticArray<T>>> {
    return StaticArray(head: lhs, tail: StaticArray(head: rhs, tail: EmptyStaticArray<T>()))
}
func !<T>(lhs: T.Item, rhs: T) -> StaticArray<T> {
    return StaticArray(head: lhs, tail: rhs)
}
// NOTE: ... and let the the concrete types conform to CollectionType instead:
extension EmptyStaticArray : CollectionType {}
extension StaticArray : CollectionType {}

let a = 1 ! 2 ! 3 ! 4 ! 5 ! 6 ! 7
for e in a { print(e) }

This little modification will make it compile fine and work as expected.

(Same behaviour in both 7.0 and 7.1 beta 2.)

0