1

Here's a support function, that I already unit-tested:

extension Collection {
    public func heapPivot(childrenPerNode: Int = 2, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Index
}

Now, I'm trying out a type that uses it:

public struct Heap<Base: RandomAccessCollection> {
    public typealias Element = Base.Element
    // more properties...
    @usableFromInline let areInIncreasingOrder: (Element, Element) -> Bool
    // more properties...
    init(_ base: Base, childrenPerNode: Int, by areInIncreasingOrder: @escaping (Element, Element) -> Bool
    )
}

I got one of the basic initializers to work:

extension Heap {
    public init?(
        confirming base: Base,
        childrenPerNode: Int = 2,
        by areInIncreasingOrder: @escaping (Element, Element) -> Bool
    ) {
        let limit = base.heapPivot(childrenPerNode: childrenPerNode,
                                   by: areInIncreasingOrder)
        guard limit == base.endIndex else { return nil }

        self.init(base, childrenPerNode: childrenPerNode,
                  by: areInIncreasingOrder)
    }
}

But when I tried to make an initializer that stops at just the matching prefix:

extension Heap /*where Base.SubSequence == Base*/ {
    public init<T: RandomAccessCollection>(
        prefixOf base: T,
        childrenPerNode: Int = 2,
        by areInIncreasingOrder: @escaping (Element, Element) -> Bool
    ) where T.SubSequence == Base {
        let limit = base.heapPivot(childrenPerNode: childrenPerNode, by: areInIncreasingOrder) // 1
        self.init(base[..<limit], childrenPerNode: childrenPerNode, by: areInIncreasingOrder)
    }
}

The compiler chokes. On the line marked (1), the compiler flags on the "h" of the .heapPivot call:

Type of expression is ambiguous without more context

(Let's call it Version 1.) When I change the constraint on T to Collection, since only the directly used type needs to be random-access, I get an improvement(?):

Cannot convert value of type '(Heap<Base>.Element, Heap<Base>.Element) -> Bool' (aka '(Base.Element, Base.Element) -> Bool') to expected argument type '(T.Element, T.Element) throws -> Bool'

and it's on the "a" of the areInIncreasingOrder argument reference. (Let's call it Version 2.)

It seems like the original code should have worked, even before I un-refined the constraint to Collection. With the T.SubSequence == Base constraint, aren't Base.Element and T.Element the same type? I first wondered if the compiler couldn't see that, but adding a

T.Element == Base.Element

constraint didn't improve matters (still Version 2).

Is this a bug? Or did I miss something?

...

When I changed line (1) to:

let limit: Base.Index = base.heapPivot(childrenPerNode: childrenPerNode, by: areInIncreasingOrder)

to force the issue, I got different errors

  • Line (1) still had the Version 2 error but added:

    Cannot convert value of type 'T.Index' to specified type 'Base.Index'

  • The last line gained two errors.

    Cannot convert value of type 'T.SubSequence' to expected argument type 'Base'
(Had fix-it to "Insert ' as! Base'.")
Subscript 'subscript(_:)' requires the types 'T.Index' and 'Base.Index' be equivalent

Why is the matching broken?! I already constrained T.SubSequence to be the same as Base, and so their Element types should be the same, and their Index types should be the same.

Oh, I changed the explicit Base.Index typing to T.Index, line (1) had the Version 2 error by itself. And the following line kept the only first error and its Fix-it.

2

When in doubt, shrink the reproducer:

struct Heap<Base> {
  var storage: Base

  init<T: Collection>(base: T) where T.SubSequence == Base {
    // Cannot assign value of type 'T.SubSequence' to type 'Base'
    storage = base[...]
  }
}

Looks like a bug to me.

3

Filed at SR-13723, "Generic initializer with constrained parameter of generic structure doesn't recognize when the structure's generic parameter matches"