[Regression] Ambiguous makeIterator() in 5.7

[LucianoPAlmeida]

Describe the bug
The following snippet

struct S: Sequence {
  private var _storage: [UInt8] = []
  func makeIterator() -> Array<UInt8>.Iterator {
    _storage.makeIterator()
  }
  
  typealias Element = UInt8
  class Iterator: IteratorProtocol {
    func next() -> UInt8? { 0 }
    typealias Element = UInt8
  }

  func makeIterator() -> Iterator {
    Iterator()
  }
}

extension S {
  func f() {
    for elt in self { //  error: ambiguous use of 'makeIterator()'
      print(elt)
    }
  }
}

Steps To Reproduce
Steps to reproduce the behavior:

1. Open this on Compiler Explorer https://godbolt.org/z/7seohEf8K
2. Note that in 5.6 that compiles but 5.7 and main nightly it gives as ambiguous makeIterator()
   ...

Expected behavior
Should compile

Screenshots
If applicable, add screenshots to help explain your problem.

Environment (please fill out the following information)

• OS: [e.g. macOS 11.0]
• Xcode Version/Tag/Branch:

Additional context

...
Resolved overloads:
  selected overload set choice self: $T0 == S for locator@0xbbc9e48 [DeclRef@<source>:23:16]
  selected overload set choice $elt$generator: $T4 == @lvalue $T2 for locator@0xbbca298 [DeclRef@<invalid loc>]
  ($T6 [attributes: delayed] [involves_type_vars: $T8] [with possible bindings: (subtypes of) $T8?])
  (attempting disjunction choice $T1 bound to decl output.(file).S.makeIterator()@<source>:4:8 : (S) -> () -> Array<UInt8>.Iterator [[locator@0xbbc9eb8 [UnresolvedDot@<source>:23:16 -> member]]];
    (overload set choice binding $T1 := () -> Array<UInt8>.Iterator)
    (overload set choice binding $T5 := () -> $T9.Element?)
    (attempting disjunction choice UInt8? bind $T8? [deep equality] [[locator@0xbbca5c0 [DeclRef@<source>:23:16 -> sequence element type -> optional payload]]];
      ($T7 [with possible bindings: (supertypes of) UInt8])
      Initial bindings: $T7 := UInt8
      (attempting type variable $T7 := UInt8
        (found solution: <default 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0>)
      )
    )
  )
  (attempting disjunction choice $T1 bound to decl output.(file).S.makeIterator()@<source>:14:8 : (S) -> () -> S.Iterator [[locator@0xbbc9eb8 [UnresolvedDot@<source>:23:16 -> member]]];
    (overload set choice binding $T1 := () -> S.Iterator)
    (overload set choice binding $T5 := () -> UInt8?)
    (attempting disjunction choice UInt8? bind $T8? [deep equality] [[locator@0xbbca5c0 [DeclRef@<source>:23:16 -> sequence element type -> optional payload]]];
      ($T7 [with possible bindings: (supertypes of) UInt8])
      Initial bindings: $T7 := UInt8
      (attempting type variable $T7 := UInt8
        (found solution: <default 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0>)
      )
    )
  )
  (attempting disjunction choice $T1 bound to decl Swift.(file).Sequence extension.makeIterator() : <Self where Self : Sequence, Self == Self.Iterator> (__owned Self) -> () -> Self [[locator@0xbbc9eb8 [UnresolvedDot@<source>:23:16 -> member]]];
    (failed constraint $T10 bind $T10.Iterator [[locator@0xbc10788 [UnresolvedDot@<source>:23:16 -> member -> opened generic -> type parameter requirement #1 (same-type)]]];)
    (overload set choice binding $T1 := () -> $T10)
  )

Maybe there is a bit more to it, but is a bit strange that the overload that is not the one from Sequence conformance is being considered here and even if considered how it is ending up with the same score.

[LucianoPAlmeida]

cc @xedin

[LucianoPAlmeida]

Ah I see that the way for-in statements are type-checked changed in #59003

[xedin]

Now next and makeIterator type-checked and ranked together instead of being picked during SILGen.

[xwu]

Hold up, does #59003 mean that I can now trick the compiler to iterate over a sequence without using its conformance to Sequence, because it's synthesizing a call to any method named makeIterator and not necessarily the one that fulfills the protocol requirement?

Compose that with our ad-hoc rule that the standard library gets shadowed by any user code, and that would mean that any library can now hijack a user's values that are of a standard library collection type, changing iteration in either obvious or subtly different ways, simply by implementing a makeIterator overload of their choosing.

This indeed seems to work:

extension Array where Element == Double {
  func makeIterator() -> Array<Int>.Iterator {
    return [1, 2, 3].makeIterator()
  }
}

for i in [4.0, 5.0, 6.0] {
  print(i)
}

// Prints (as of Swift 5.7, but not in Swift 5.6):
// 1
// 2
// 3

This seems...bad?

[xedin]

The implementation follows overloading rules like all other code that could be written by hand calling makeIterator() on a type that conforms to a Sequence protocol.

[xwu]

For better or for worse, for...in iteration in Swift is modeled via protocol conformance to Sequence; until now, it was the implementation of makeIterator() that satisfies the protocol requirement—not whatever overload is utterable and wins overload resolution—that makes the iterator used for looping.

Changing the implementation causes a number of invariants to be broken:

1. The way in which a type conforms to a protocol cannot be changed retroactively—a user can retroactively conform a type to a protocol that the type didn't conform to before, but they cannot change how an existence conformance is implemented. Since for...in iteration is supported by a protocol conformance, this means that a user cannot retroactively change how a type that already conforms to Sequence iterates over its elements. With [TypeChecker] Rework type-checking of for-in statements #59003, users now can.
2. A type can conform to a protocol only once—when a generic type unconditionally conforms to a protocol, then there cannot be a different conformance that vary based on its generic parameters. Since for...in iteration is supported by a protocol conformance, this means that there can be only one way of iterating over a sequence of generic type. With [TypeChecker] Rework type-checking of for-in statements #59003, this no longer holds true.

IMO, this is a significant change to user-visible behavior of the language which, even if desired (I am very wary of this), should be reviewed by the language workgroup. Effectively, it amounts to deleting makeIterator as an ordinary protocol requirement and aligning the design with other "magical" methods such as callAsFunction.

[xedin]

Okay, let’s consider this new behavior a bug and restrict it like before, but that would mean that the code written via direct makeIterator() call with while let would behave differently from for-in which goes against the documentation of IteratorProtocol from stdlib - https://github.com/apple/swift/blob/149e57a0cbe619386d6287c18e2eb6289735e7d9/stdlib/public/core/Sequence.swift#L39

[xwu]

In the specific example given in documentation, the text is accurate: the makeIterator written manually is exactly that which fulfills the protocol requirement of Sequence and gets used for iterating in the for-in loop. The documentation does not claim that this is a verbatim desugaring like we do for result builders, etc.

It would be possible, I’d assume, to implement the Swift 5.6 behavior by instead desugaring to an inlined call to a generic function that operates on some Sequence?

Let me bring this up with the workgroup at our next meeting and see if others have thoughts on the change.

[xedin]

It would be possible, I’d assume, to implement the Swift 5.6 behavior by instead desugaring to an inlined call to a generic function that operates on some Sequence?

Yes for non-existential types could be inject additional $<name> variable with a contextual type of some Sequence and use that i.e.:

func test(arr: [Int]) {
  let $arr: some Sequence = arr
  var $arr$generator = $arr.makeIterator()

  while let v = $arr$generator.next() {
    print(v)
  }
}

But this would not work for any Sequence which we'd like to support as well if could only be opened if it's a base of .makeIterator() call, and we cannot always know the type of for-in expression in advance due to overloading, that's why it seemed reasonable to use original expression as a base of synthesized .makeIterator() call and let overloading do the rest which also consistent with code that users would write by hand.

All that said I think we still could return back to original behavior via a special constraint (instead of .makeIterator() call) which is going to lookup conformance to Sequence and retrieve corresponding witness declaration, it would definitely work for conforming types but I'm not (yet) sure about existentials.

/cc @hborla

[xedin]

I'll try to see whether we can get away with ranking of witness makeIterator higher than non-witness one in sequence expression context (as an alternative approach which is less invasive).