[SR-2819] Commit d9650fb breaks dual conforming RandomAccessCollection, RangeReplaceableCollection collections. #45423

swift-ci · 2016-10-02T09:43:44Z


Previous ID	SR-2819
Radar	None
Original Reporter	mattgallagher (JIRA User)
Type	Bug

Additional Detail from JIRA


Votes	0
Component/s	Standard Library
Labels	Bug
Assignee	None
Priority	Medium

md5: fc76bbdc66732e5a4a9aca424ccb88e0

Issue Description:

The following code fails to compile in the 2016-10-01 snapshot, despite working in previous Swift 3 builds:

struct SomeCollection<T>: RandomAccessCollection, RangeReplaceableCollection {
   typealias Index = Int
   typealias Indices = CountableRange<Int>
   var startIndex: Index { return 0 }
   var endIndex: Index { return 0 }
   subscript(_ at: Index) -> T {
      get { preconditionFailure() }
   }
   var indices: Indices {
      return CountableRange(uncheckedBounds: (lower: startIndex, upper: endIndex))
   }
   func index(after i: Int) -> Int {
      return i + 1
   }
   func index(before i: Int) -> Int {
      return i - 1
   }
   mutating func replaceSubrange<C>(_ subrange: Range<Int>, with newElements: C) where C: Collection, C.Iterator.Element == T {
   }
}

Remove either of the `RandomAccessCollection` or `RangeReplaceableCollection` conformances and it will compile. Build in an earlier version of Swift (e.g. Xcode 8 or Xcode 8.1 beta 1) and there's no problem.

The issue appears to be ambiguity problems around `SubSequence` that cannot be easily resolved.

/Users/matt/collection_problem/collection_problem/main.swift:24:8: error: type 'SomeCollection<T>' does not conform to protocol '_IndexableBase'
struct SomeCollection<T>: RandomAccessCollection, RangeReplaceableCollection {
       ^
Swift._IndexableBase:51:20: note: ambiguous inference of associated type 'SubSequence': 'Slice<SomeCollection<T>>' vs. 'BidirectionalSlice<SomeCollection<T>>'
    associatedtype SubSequence
                   ^
Swift.Collection:25:12: note: matching requirement 'subscript' to this declaration inferred associated type to 'Slice<SomeCollection<T>>'
    public subscript(bounds: Range<Self.Index>) -> Slice<Self> { get }
           ^
Swift.BidirectionalCollection:5:12: note: matching requirement 'subscript' to this declaration inferred associated type to 'BidirectionalSlice<SomeCollection<T>>'
    public subscript(bounds: Range<Self.Index>) -> BidirectionalSlice<Self> { get }
           ^
/Users/matt/collection_problem/collection_problem/main.swift:24:8: error: type 'SomeCollection<T>' does not conform to protocol 'RangeReplaceableCollection'
struct SomeCollection<T>: RandomAccessCollection, RangeReplaceableCollection {
       ^
Swift.RangeReplaceableCollection:49:20: note: protocol requires nested type 'SubSequence'; do you want to add it?
    associatedtype SubSequence : _RangeReplaceableIndexable = RangeReplaceableSlice<Self>
                   ^
/Users/matt/collection_problem/collection_problem/main.swift:24:8: error: type 'SomeCollection<T>' does not conform to protocol 'BidirectionalCollection'
struct SomeCollection<T>: RandomAccessCollection, RangeReplaceableCollection {
       ^
Swift.BidirectionalCollection:40:20: note: protocol requires nested type 'SubSequence'; do you want to add it?
    associatedtype SubSequence : _BidirectionalIndexable, Collection = BidirectionalSlice<Self>
                   ^
/Users/matt/collection_problem/collection_problem/main.swift:24:8: error: type 'SomeCollection<T>' does not conform to protocol '_RangeReplaceableIndexable'
struct SomeCollection<T>: RandomAccessCollection, RangeReplaceableCollection {
       ^
Swift._RangeReplaceableIndexable:18:12: note: protocol requires initializer 'init(repeating:count:)' with type '(repeating: Self._Element, count: Int)'; do you want to add a stub?
    public init(repeating repeatedValue: Self._Element, count: Int)
           ^
Swift.RangeReplaceableCollection:17:24: note: candidate has non-matching type '(repeating: Self.Iterator.Element, count: Int)'
    public convenience init(repeating repeatedValue: Self.Iterator.Element, count: Int)
                       ^
/Users/matt/collection_problem/collection_problem/main.swift:24:8: error: type 'SomeCollection<T>' does not conform to protocol 'Collection'
struct SomeCollection<T>: RandomAccessCollection, RangeReplaceableCollection {
       ^
Swift.Collection:149:20: note: protocol requires nested type 'SubSequence'; do you want to add it?
    associatedtype SubSequence : _IndexableBase, Sequence = Slice<Self>
                   ^
Swift.Collection:140:20: note: default type 'IndexingIterator<SomeCollection<T>>' for associated type 'Iterator' (from protocol 'Collection') does not conform to 'IteratorProtocol'
    associatedtype Iterator : IteratorProtocol = IndexingIterator<Self>
                   ^
/Users/matt/collection_problem/collection_problem/main.swift:24:8: error: type 'SomeCollection<T>' does not conform to protocol 'Sequence'
struct SomeCollection<T>: RandomAccessCollection, RangeReplaceableCollection {
       ^
Swift.Sequence:120:20: note: protocol requires nested type 'Iterator'; do you want to add it?
    associatedtype Iterator : IteratorProtocol
                   ^
/Users/matt/collection_problem/collection_problem/main.swift:24:8: error: type 'SomeCollection<T>' does not conform to protocol 'RandomAccessCollection'
struct SomeCollection<T>: RandomAccessCollection, RangeReplaceableCollection {
       ^
Swift.RandomAccessCollection:24:20: note: protocol requires nested type 'SubSequence'; do you want to add it?
    associatedtype SubSequence : _RandomAccessIndexable, BidirectionalCollection = RandomAccessSlice<Self>

The commit responsible is d9650fb:

d9650fb

Reverting this commit eliminates the problem. I'm stopping short of a pull request that reverts this commit but I think it should be considered.

It's possible that there's a smarter way to resolve the ambiguity that I'm not seeing. Perhaps it's considered nonsensical to implement both these protocols? Perhaps simply better fix suggestions are required to guide towards a solution?

The text was updated successfully, but these errors were encountered:

belkadan · 2016-10-03T18:23:34Z

cc @moiseev

moiseev · 2016-10-03T18:38:35Z

A simple fix would be to explicitly say what your slice is. There is `RangeReplaceableRandomAccessSlice`. It might not be enough to simply say `typealias SubSequence = RangeReplaceableRandomAccessSlice<..>` though. What usually works is overriding a subscript that will simply construct the said slice instance.

As for the proper fix, I think, providing an `extension RandomAccessCollection where Self == RangeReplaceableCollection { ... }` with the same kind of subscript implementation as described above, should solve it.

mattgallagher (JIRA User), do you mind trying it and submitting a PR maybe? It would also be great to include a test case for this particular issue.

belkadan · 2016-10-03T18:42:16Z

I actually had trouble using the explicit typealias in a personal project the other day, but haven't had the chance to file the issue. The compiler detects a circularity in passing the Self type as the generic parameter to the slice, and rejects the conformance. I had to trick it by writing the slicing subscript and having it infer the type.

moiseev · 2016-10-03T18:49:27Z

@belkadan We saw multiple instances of this problem while implementing the new indexing model, so I believe there is already a radar for that. And yes, you're right, implementing a subscript usually helps.

swift-ci · 2016-10-04T07:20:05Z

Comment by Matt Gallagher (JIRA)

@moiseev as @belkadan mentions, attempting to explicitly set the typealias in the type as follows:

typealias SubSequence = RangeReplaceableRandomAccessSlice<Self>

gives the error "Type alias `SubSequence` circularly references itself".

I didn't think to try implementing the `subscript(:Range<Index>)` operator. That does offer a useable workaround for the problem when the `subscript` is defined on the type itself.

However, your suggested fix in the standard library – defining the `subscript` in an extension – does not appear work. The following extension:

 extension RandomAccessCollection where Self: RangeReplaceableCollection {
    public subscript(bounds: Range<Self.Index>) -> RangeReplaceableRandomAccessSlice<Self> {
        return RangeReplaceableRandomAccessSlice(base: self, bounds: bounds)
    }
}

merely appears to create further ambiguity (causing errors all over the standard library). I also tried adding `SubSequence == RangeReplaceableRandomAccessSlice<Self>` to the extension constraints, to no avail.

moiseev · 2016-10-04T18:34:58Z

Well.. It was worth trying at least. Thanks for sharing your experience. Does it mean that your immediate problem was solved by introducing the subscript? Or do you need another solution?

swift-ci · 2016-10-05T02:45:58Z

Comment by Matt Gallagher (JIRA)

@moiseev My specific use case is solved with the subscript, yes.

I'll leave it to you guys to decide if you want to take further steps or close this issue as "work around available" for now. Frankly, I think the biggest problem is the limitation imposed by the "Type alias `SubSequence` circularly references itself" but I'm sure you have bugs to fix that already.

slavapestov · 2016-12-23T18:35:31Z

The "Type alias `SubSequence` circularly references itself" thing is fixed on master.

swift-ci transferred this issue from apple/swift-issues Apr 25, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

[SR-2819] Commit d9650fb breaks dual conforming RandomAccessCollection, RangeReplaceableCollection collections. #45423

[SR-2819] Commit d9650fb breaks dual conforming RandomAccessCollection, RangeReplaceableCollection collections. #45423

swift-ci commented Oct 2, 2016

belkadan commented Oct 3, 2016

moiseev mannequin commented Oct 3, 2016

belkadan commented Oct 3, 2016

moiseev mannequin commented Oct 3, 2016

swift-ci commented Oct 4, 2016

moiseev mannequin commented Oct 4, 2016

swift-ci commented Oct 5, 2016

slavapestov commented Dec 23, 2016

[SR-2819] Commit d9650fb breaks dual conforming RandomAccessCollection, RangeReplaceableCollection collections. #45423

[SR-2819] Commit d9650fb breaks dual conforming RandomAccessCollection, RangeReplaceableCollection collections. #45423

Comments

swift-ci commented Oct 2, 2016

belkadan commented Oct 3, 2016

moiseev mannequin commented Oct 3, 2016

belkadan commented Oct 3, 2016

moiseev mannequin commented Oct 3, 2016

swift-ci commented Oct 4, 2016

moiseev mannequin commented Oct 4, 2016

swift-ci commented Oct 5, 2016

slavapestov commented Dec 23, 2016