[swift-evolution] Marking sort and sorted with rethrows

[Brent Royal-Gordon]

> 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. 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. 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
			…
		}
	}

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.

* * *

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.

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 }
	}

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. 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 }
	 }

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 }
	 }

-- 
Brent Royal-Gordon
Architechies