[swift-evolution] Marking sort and sorted with rethrows

[Dave Abrahams]

on Wed Jun 08 2016, Brent Royal-Gordon <brent-AT-architechies.com> wrote:

>> I'm not sure that these ideas are consistent with the Swift
>> error-handling philosophy, which IIUC is very consciously designed *not*
>> to support things like file- and database-backed Collections.  My
>> understanding is that if you have something like that, you're not
>> supposed to throw errors on failure, but instead find some alternative
>> means of error handling.  These cases seem very much in the same
>> ballpark.
>
> I'm not talking about the Collection itself being backed by a file,
> but rather the instances inside it being backed by a file. 

Those amount to the same thing.  If instances can be backed by a file,
subscripting needs to be able to throw, and therefore practically every
generic function (or protocol extension method) on Collection would also
need to be marked as throwing.  When Swift error handling was designed,
it was decided that these cases were out-of-scope.

> I suppose you're trying to acknowledge that distinction when you say
> these cases are "in the same ballpark", but I don't think that's
> really a sustainable objection.

Why not?

> There *are* sensible alternatives, like the early-terminating block
> pattern, to throwing sequences and perhaps even throwing collections:
>
> 	try database.withQuery(sql) { rows in
> 		for row in rows {
> 			// If fetching a row fails, this loop terminates early and `withQuery` throws
> 			…
> 		}
> 	}

That strategy doesn't begin to cover the use cases for collections.

Also, how is it supposed to work? You need a way to report a failure to
fetch the row—a way that doesn't involve throwing.  Who terminates the
loop, and how?  How does withQuery detect that the loop exited early?

> But throwing operations on stuff-inside-a-collection? That's just part
> of the language, and making errors during sorting extraordinarily
> difficult to handle won't stop the errors from being possible.

There's basically no distinction.  If it's reasonable to have sort with
a throwing predicate, it's also reasonable to have a Comparable type
whose < operator throws, and it's reasonable to use the sort overload
that takes no explicit predicate, and now you have a Collection protocol
method that throws directly, rather than rethrowing.  IIUC from the
people who designed Swift error handling, if you find yourself doing
that, you've done something wrong.

> * * *
>
> I actually think there *is* a sensible way to define the behavior of a
> throwing `sort(_:)`: you treat the comparison as though it returned
> `false` and continue sorting. 
> If there's any sort of stability to the errors being thrown by
> `isOrderedBefore`, this will end up behaving like a sort with
> unordered elements, much like an array of floating-point types with
> some NaNs in it. You not be able to rethrow all of the errors
> encountered during the sort—you'd have to pick the first or last—but a
> representative error would probably cover the use cases here.

As Dmitri pointed out, that predicate doesn't satisfy the requirements
for sorting.  It's quite possible that a predicate that doesn't satisfy
an algorithm's requirements causes the algorithm to do invalid indexing
or some other evil nonsense.

> You could implement this with today's Swift in terms of our existing `sort(_:)`:
>
> 	mutating func sort(isOrderedBefore: (Element, Element) throws -> Bool) throws {
> 		var lastError: Error?
>
> 		sort {
> 			do {
> 				return try isOrderedBefore($0, $1)
> 			}
> 			catch {
> 				lastError = error
> 				return false
> 			}
> 		}
>
> 		if lastError = lastError { throw lastError }
> 	}

Aside from the problems mentioned above, this is extremely inefficient
if the collection is large and backed a resource that fails slowly, such
as a network connection with retry and timeout.

> I don't think you could currently do one version with `rethrows`,
> because any way you do this, you'll need to save an error in a
> variable and `throw` it later, which I don't believe `rethrows` will
> permit. 

Right.  That's a problem with the error-handling model.

> However, I saw a suggestion in the bottom type thread that, given both
> a `throws` keyword that can take an error type and a bottom type to
> represent the error type of a non-throwing function, `rethrows` could
> essentially be syntactic sugar for a function with a generic error
> type. This would give us additional flexibility in cases like this
> where `rethrows` doesn't quite do what we need.
>
> With the necessary features in place, we could implement a `rethrows`-ish `sort(_:)` like this:
>
> 	// This declaration has rethrows-like behavior: if `isOrderedBefore`'s error type is `Never`, then 
> 	// `sort(_:)`'s error type is also `Never`, and there's no reason to require a `try` on the call to this method.
> 	mutating func sort<Error: ErrorProtocol>(isOrderedBefore: (Element, Element) throws Error -> Bool) throws Error {
> 		var lastError: Error?
>
> 		func isOrderedBeforeWithUnorderedErrors(a: Element, b: Element) -> Bool {
> 			do {
> 				return try isOrderedBefore(a, b)
> 			}
> 			catch {
> 				lastError = error
> 				return false
> 			}
> 		}
>
> 		// Do the actual sorting here.
>
> 		if lastError = lastError { throw lastError }
> 	 }

That's cute, but IIUC the designers of the error handling model
explicitly did *not* want to thread throwing-ness through generics in
this way.  This is roughly the same mechanism as would be required to
accomplish other things I'd like to see, like the
sorting-throwing-Comparables thing I mentioned above, but that were
designed out of the model.

FWIW, it would need to be generalized further, in case there were two
operations that throw different Error types.  Also, I know some will
disagree, but IMO you really don't want to get into a situation where
people are annotating most throwing functions with the exact Error types
that can be thrown.

You need a way to express the type

    if (E0, E1, ... EN).contains(Bottom) then Bottom else ErrorProtocol

where Ei is one of the thrown error types, and for protocol methods that
are not marked with an explicit throws annotation, that type should be
synthesized automatically from the error types that can propagate from
any operations in protocol dependencies... but ah, as I say, IIUC this
sort of thing was designed out of the model.  

My point isn't that what you're trying to do is wrong.  My point is that
it seems inconsistent with the Swift approach to error-handling, and
that if you want to do these things, you may need to convince someone to
change that approach.

> With a fair bit of work, it might even be possible to allow it to throw *all* of the errors it encountered:
>
> 	// This is structured slightly strangely to ensure that, if Error is Never, then MultipleErrors<Never> 
> 	// is an empty enum (since all cases require a Never associated value), and thus (hopefully!) 
> 	// is itself a synonym for Never.
> 	enum MultipleErrors<Error: ErrorProtocol>: ErrorProtocol {
> 		case one (Error)
> 		indirect case many (Error, ErrorList<Error>)
>
> 		func appending(_ newError: Error) -> MultipleErrors<Error> {
> 			switch self {
> 			case let .one(oldError):
> 				return .many(oldError, .one(newError))
> 			case let .many(firstError, restErrors):
> 				return .many(firstError, restErrors.appending(newError))
> 			}
> 		}		
> 	}
>
> 	extension<Error: ErrorProtocol> Optional where Wrapped == MultipleErrors<Error> {
> 		func appending(_ newError: Error) -> MultipleErrors<Error>? {
> 			switch self {
> 			case .none:
> 				return .some(.one(newError))
> 			case .some(let errors):
> 				return .some(errors.appending(newError))
> 			}
> 		}
> 	}
>
> 	mutating func sort<Error: ErrorProtocol>(isOrderedBefore: (Element, Element) throws Error -> Bool) throws MultipleErrors<Error> {
> 		var errors: MultipleErrors<Error>?
>
> 		func isOrderedBeforeWithUnorderedErrors(a: Element, b: Element) -> Bool {
> 			do {
> 				return try isOrderedBefore(a, b)
> 			}
> 			catch {
> 				errors = errors.appending(error)
> 				return false
> 			}
> 		}
>
> 		// Do the actual sorting here.
>
> 		if errors = errors { throw errors }
> 	 }

IMO that would be a collosal waste of resources.  The only interesting
error is the first one.  This is notionally a sort that failed partway
through, and that we had no mechanism for interrupting.  The fact that
you have to continue sorting after that error is just an artifact of
language limitations.  Either we should reaffirm our current (implicit)
declaration that these kinds of use-cases are off the table for Swift
error handling, or the philosophy of Swift error-handling should change
to allow us to support stopping at the right time.

-- 
Dave