[Draft] Change IteratorType post-nil guarantee


(Patrick Pijnappel) #1

Proposal pull request: #213
<https://github.com/apple/swift-evolution/pull/213>
Implementation pull request: #1702
<https://github.com/apple/swift/pull/1702>
Original pitch thread: [Proposal] Change guarantee for GeneratorType.next()
to always return nil past end
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/8519>

Change IteratorType post-nil guarantee

   - Proposal: SE-NNNN
   <https://github.com/apple/swift-evolution/blob/master/proposals/NNNN-name.md>
   - Author(s): Patrick Pijnappel <https://github.com/PatrickPijnappel>
   - Status: *Awaiting review*
   - Review manager: TBD

<https://github.com/PatrickPijnappel/swift-evolution/blob/patch-1/proposals/XXXX-iterator-post-nil-guarantee.md#introduction>
Introduction

Currently, the documentation for IteratorType.next() has the precondition
that when calling next(), no preceding call to next() should have returned
nil, and in fact encourages implementations to raise a
preconditionFailure() for
violations of this requirement. However, all current 27 IteratorType
implementations
in the standard library return nil indefinitely. Many users are likely
unaware of the precondition, expecting all iterators to return nil indefinitely
and writing code that might rely on this assumption. Such code will usually
run fine, until someone does in fact pass in an iterator not repeating
nil (it's
a silent corner case).

Swift-evolution thread: [Proposal] Change guarantee for
GeneratorType.next() to always return nil past end
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/8519>

Pull-request: #1702 <https://github.com/apple/swift/pull/1702>
<https://github.com/PatrickPijnappel/swift-evolution/blob/patch-1/proposals/XXXX-iterator-post-nil-guarantee.md#motivation>
Motivation

While not overwhelmingly common, it is relatively easy to write code based
on the assumption nil will be returned indefinitely:

// Example based on standard library code (Sequence.swift)while let
element = iterator.next() {
  if condition(element) {
    foo(element) // call foo on first element satisfying condition
    break
  }
}while let element = iterator.next() {
  bar(element) // call bar on remaining elements
}
// Another exampleswitch (iterator.next(), iterator.next()) {// ...
}

Even though this can be trivially rewritten to not rely on post-nil behavior,
the user won't perform this rewrite if they are unaware of the
precondition. In their testing the code will work fine, and likely will in
almost every case, except when passing the rare iterator that doesn't
repeat nil.
<https://github.com/PatrickPijnappel/swift-evolution/blob/patch-1/proposals/XXXX-iterator-post-nil-guarantee.md#proposed-solution>Proposed
solution

Bring the guarantee in line with the common expectation, and require
iterators to return nil indefinitely.

Requiring nil to be returned indefinitely does require the implementors of
custom IteratorType conformances to respect this, but this is likely
already the expectation for most users. Most iterators already get this as
a natural consequence of their implementation (as is the case with
all current standard library iterators), but otherwise they can simply
track a done flag to do so. It should be noted that this requirement would
also affect closures passed to AnyIterator.
<https://github.com/PatrickPijnappel/swift-evolution/blob/patch-1/proposals/XXXX-iterator-post-nil-guarantee.md#performance-considerations>Performance
considerations

The original rationale for introducing the precondition was because of
concerns it might add storage and performance burden to some
implementations of IteratorType (see here
<http://article.gmane.org/gmane.comp.lang.swift.evolution/8532>).

However, in light of implementation experience, there are a few
observations we can make:

   - These cases are rare. The standard library currently has no iterators
   that require extra state or branches to return nilindefinitely. The
   iterator for the proposed takeWhile() (SE-0045
   <https://github.com/apple/swift-evolution/blob/master/proposals/0045-scan-takewhile-dropwhile.md>)
   would be the first occurance in the standard library.
   - Even in such cases, in the common case the calling code doesn't rely
   on post-nil behavior (e.g. for in, map, etc.) this extra storage and
   branching can usually optimized away.
   - Not having the post-nil guarantee can sometimes add storage and
   performance burden for the caller instead, e.g. when an iterator somehow
   buffers it's underlying iterator. This in contrast can usually not be
   optimized away. For example, the standard library's UTF8/UTF16 decoding has
   4 instead of 3 branches per character for ASCII because of this.

<https://github.com/PatrickPijnappel/swift-evolution/blob/patch-1/proposals/XXXX-iterator-post-nil-guarantee.md#detailed-design>Detailed
design

Original guarantee:

/// Advance to the next element and return it, or `nil` if no next///
element exists.////// - Precondition: `next()` has not been applied to
a copy of `self`/// since the copy was made, and no preceding call
to `self.next()`/// has returned `nil`. Specific implementations of
this protocol /// are encouraged to respond to violations of
this requirement by /// calling `preconditionFailure("...")`.

Proposed guarantee:

/// Advance to the next element and return it, or `nil` if no next
element/// exists. Once `nil` has been returned, all subsequent calls
return `nil`.////// - Precondition: `next()` has not been applied to a
copy of `self`/// since the copy was made.

<https://github.com/PatrickPijnappel/swift-evolution/blob/patch-1/proposals/XXXX-iterator-post-nil-guarantee.md#impact-on-existing-code>Impact
on existing code

All IteratorType implementations in the standard library already comply
with the new guarantee. It is likely most existing custom iterators will as
well, however some might be rendered in violation of their guarantee by the
change.
<https://github.com/PatrickPijnappel/swift-evolution/blob/patch-1/proposals/XXXX-iterator-post-nil-guarantee.md#alternatives-considered>Alternatives
considered

   - Require IteratorType to not crash but keep the return value up to
   specific implementations. This allows them to use it for other behavior
   e.g. repeating the sequence after nil is returned. This however retains
   most of the problems of the original guaranteee described in this proposal.


(Erica Sadun) #2

What about Kevin's Rust-like approach (the fuse) as an alternative considered?
He suggested that instead of changing the guarantees and behavior of the existing
GeneratorType, that Swift introduce a new FuseGenerator adaptor that could include
extra state ensuring that it could safely return nil indefinitely as Rust does

-- E

···

On Mar 17, 2016, at 11:47 PM, Patrick Pijnappel via swift-evolution <swift-evolution@swift.org> wrote:

Proposal pull request: #213 <https://github.com/apple/swift-evolution/pull/213>
Implementation pull request: #1702 <https://github.com/apple/swift/pull/1702>
Original pitch thread: [Proposal] Change guarantee for GeneratorType.next() to always return nil past end <http://thread.gmane.org/gmane.comp.lang.swift.evolution/8519>

Alternatives considered

Require IteratorType to not crash but keep the return value up to specific implementations. This allows them to use it for other behavior e.g. repeating the sequence after nil is returned. This however retains most of the problems of the original guaranteee described in this proposal.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Patrick Pijnappel) #3

What about Kevin's Rust-like approach (the fuse) as an alternative
considered?
He suggested that instead of changing the guarantees and behavior of the
existing
GeneratorType, that Swift introduce a new FuseGenerator adaptor that could
include
extra state ensuring that it could safely return nil indefinitely as Rust
does

I'll include a section about that!

···

On Sat, Mar 19, 2016 at 1:16 AM, Erica Sadun <erica@ericasadun.com> wrote:

What about Kevin's Rust-like approach (the fuse) as an alternative
considered?
He suggested that instead of changing the guarantees and behavior of the
existing
GeneratorType, that Swift introduce a new FuseGenerator adaptor that could
include
extra state ensuring that it could safely return nil indefinitely as Rust
does

-- E

On Mar 17, 2016, at 11:47 PM, Patrick Pijnappel via swift-evolution < > swift-evolution@swift.org> wrote:

Proposal pull request: #213
<https://github.com/apple/swift-evolution/pull/213>
Implementation pull request: #1702
<https://github.com/apple/swift/pull/1702>
Original pitch thread: [Proposal] Change guarantee for
GeneratorType.next() to always return nil past end
<http://thread.gmane.org/gmane.comp.lang.swift.evolution/8519>

Alternatives considered

   - Require IteratorType to not crash but keep the return value up to
   specific implementations. This allows them to use it for other behavior
   e.g. repeating the sequence after nil is returned. This however
   retains most of the problems of the original guaranteee described in this
   proposal.

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Patrick Pijnappel) #4

Post-nil behavior being relevant is somewhat rare either way, but a
comparison:

*Current – post-nil unspecified*
– Responsibility of the caller, needs to be aware of the API contract and
needs to track a bool and branch when relying on post-nil.
– Standard library currently has 3 occurrences of this being necessary.
– As all stdlib iterators do repeat nil indefinitely, many people likely
assume relying on this is OK.
– Branch and state can usually not be optimized away. Though performance is
not the key concern, iterators are often used in tight loops and can affect
very commonly used algorithms (to take the stdlib example of ASCII
decoding, it would be 25% faster with the proposed guarantee).

*Proposed – post-nil always nil*
– Responsibility of implementor of custom iterator, needs to be aware of
the API contract and needs to track a bool and branch for some cases.
– The standard library currently has no occurrences of the being necessary.
If SE-0045 is excepted, it will introduce the first case (out of 30
iterators).
– Implementor is more likely to be aware of the API contract because a)
it's the way the stdlib iterators work b) implementors are probably more
likely than callers to check the API contract.
– Branch and state (for iterators that need it) can usually be optimized
away when not needed by caller (e.g. in a for in loop). Note that when
post-nil behavior is relied upon, the caller would have had to track state
and branch already if the iterator didn't.

The argument that it's risky to rely on people adhering to the API contract
can be made for either case:
– "Writing an iterator that doesn't repeat nil is risky as the caller might
not adhere to the API contract, so just make all iterators repeat nil
anyway."
– "Writing code that relies on the iterator repeating nil is risky as the
implementor might not adhere to the API contract, so just track state and
branch in that code anyway."
But protecting both sides kinda defeats the purpose of the API contract IMO.


(Brent Royal-Gordon) #5

Current – post-nil unspecified
– Responsibility of the caller, needs to be aware of the API contract and needs to track a bool and branch when relying on post-nil.
– Standard library currently has 3 occurrences of this being necessary.

I got curious and decided to try to locate these. I found two:

https://github.com/apple/swift/blob/a147a582fec7f0bcf058d089d79fb0950c261db9/stdlib/public/core/Sequence.swift#L435
https://github.com/apple/swift/blob/97d8f50af4978e54289377a0bd205e71a34529a2/stdlib/public/core/Zip.swift#L52

(Interestingly the Zip one is defensive programming: ZipGenerator.next() is ensuring it doesn't incorrectly call its child generators' next() methods even if is itself called too many times.)

What was the third? I must have missed it.

···

--
Brent Royal-Gordon
Architechies


(Patrick Pijnappel) #6

I wasn't counting Zip as that tracks it for different reasons (as you point
out). The remaining two are in UTF-8/UTF-16 decoding (the done flag is
inside the lookahead flags):
https://github.com/apple/swift/blob/master/stdlib/public/core/Unicode.swift#L296
https://github.com/apple/swift/blob/master/stdlib/public/core/Unicode.swift#L485

···

On Sat, Mar 19, 2016 at 2:16 PM, Brent Royal-Gordon <brent@architechies.com> wrote:

> Current – post-nil unspecified
> – Responsibility of the caller, needs to be aware of the API contract
and needs to track a bool and branch when relying on post-nil.
> – Standard library currently has 3 occurrences of this being necessary.

I got curious and decided to try to locate these. I found two:

https://github.com/apple/swift/blob/a147a582fec7f0bcf058d089d79fb0950c261db9/stdlib/public/core/Sequence.swift#L435

https://github.com/apple/swift/blob/97d8f50af4978e54289377a0bd205e71a34529a2/stdlib/public/core/Zip.swift#L52

(Interestingly the Zip one is defensive programming: ZipGenerator.next()
is ensuring it doesn't incorrectly call its child generators' next()
methods even if is itself called too many times.)

What was the third? I must have missed it.

--
Brent Royal-Gordon
Architechies