Marking sort and sorted with rethrows


(Tim Vermeulen) #1

Most standard library functions that take a closure allow that closure to throw (and those functions are subsequently marked with rethrows). sort and sorted are exceptions to this. I couldn’t find this documented anywhere, but I assume this is because sorting can happen in-place and it would be impossible to restore the array to its original state without giving up performance. Correct me if I’m wrong.

I’d like to propose that we let sort rethrow anyways, and leave the array in an intermediate state (where the elements are in an arbitrary order) when an error is thrown. As long as this is properly documented, this shouldn’t lead to any confusion. Best of all, it would allow sorted to rethrow as well in which there is no room for confusion at all because it doesn’t mutate any of the user’s variables.


(Dave Abrahams) #2

Most standard library functions that take a closure allow that closure
to throw (and those functions are subsequently marked with
rethrows). sort and sorted are exceptions to this. I couldn’t find
this documented anywhere, but I assume this is because sorting can
happen in-place and it would be impossible to restore the array to its
original state without giving up performance. Correct me if I’m wrong.

The guarantee that a function completes successfully or has no effect is
called the “strong guarantee.” There's nothing wrong, however, with
operations that only give the “basic guarantee”—that invariants are
preserved—which would leave the collection in an indeterminate state.

I’d like to propose that we let sort rethrow anyways, and leave the
array in an intermediate state (where the elements are in an arbitrary
order) when an error is thrown. As long as this is properly
documented, this shouldn’t lead to any confusion.

I have only one concern with this, which is that a completely
indeterminate state may not give us sufficient permission to detect and
prevent nonsense. Should the compiler be allowed to refuse to compile
code that can be statically shown to use partially-modified state, and
the library allowed to mark any such state as unusable at runtime?

A cheap approximation of this kind of marking for Array might be to call
`clear(keepingCapacity: true)`, in debug builds only, when an error is
thrown through a mutating method. That would (almost) ensure you had to
assign into or clear the array before doing anything with it.

When we first designed exception-safety for C++, details of the
standardization schedule made it important to reduce the model's
complexity to an absolute minimum, so we kept the idea of
unusable-until-reassigned state out of the picture. But a simple model
that makes nonsense code legal is not really in keeping with Swift,
especially when we can detect the nonsense.

Best of all, it would allow sorted to rethrow as well in which there
is no room for confusion at all because it doesn’t mutate any of the
user’s variables.

Yes, about sorted there is no question whatsoever because there is no mutation.

···

on Sun Jun 05 2016, Tim Vermeulen <swift-evolution@swift.org> wrote:

--
-Dave


(Haravikk) #3

This sounds reasonable; worst case with in-place sorting is that the collection was sorted in one order, and is only partially sorted in a new one, but the exception and your handling of it should be able to account for this.

It will require documentation to be clear that sorting methods should take care not to leave anything incomplete if a closure throws; most algorithms should be fine since they usually just test the closure then swap two values afterwards (where necessary) so there’s nothing really to interrupt, but anything that uses some kind of buffering may need to be redesigned to ensure there’s a fallback to ensure no elements are ever lost.

···

On 5 Jun 2016, at 19:14, Tim Vermeulen via swift-evolution <swift-evolution@swift.org> wrote:

Most standard library functions that take a closure allow that closure to throw (and those functions are subsequently marked with rethrows). sort and sorted are exceptions to this. I couldn’t find this documented anywhere, but I assume this is because sorting can happen in-place and it would be impossible to restore the array to its original state without giving up performance. Correct me if I’m wrong.

I’d like to propose that we let sort rethrow anyways, and leave the array in an intermediate state (where the elements are in an arbitrary order) when an error is thrown. As long as this is properly documented, this shouldn’t lead to any confusion. Best of all, it would allow sorted to rethrow as well in which there is no room for confusion at all because it doesn’t mutate any of the user’s variables.


(Dave Abrahams) #4

Ensuring that no elements are ever lost is not a particularly useful
goal, and not a constraint to which I would want to hold the standard
library.

···

on Sun Jun 05 2016, Haravikk <swift-evolution@swift.org> wrote:

On 5 Jun 2016, at 19:14, Tim Vermeulen via swift-evolution <swift-evolution@swift.org> wrote:

Most standard library functions that take a closure allow that
closure to throw (and those functions are subsequently marked with
rethrows). sort and sorted are exceptions to this. I couldn’t find

this documented anywhere, but I assume this is because sorting can
happen in-place and it would be impossible to restore the array to
its original state without giving up performance. Correct me if I’m
wrong.

I’d like to propose that we let sort rethrow anyways, and leave the
array in an intermediate state (where the elements are in an
arbitrary order) when an error is thrown. As long as this is
properly documented, this shouldn’t lead to any confusion. Best of
all, it would allow sorted to rethrow as well in which there is no
room for confusion at all because it doesn’t mutate any of the
user’s variables.

This sounds reasonable; worst case with in-place sorting is that the
collection was sorted in one order, and is only partially sorted in a
new one, but the exception and your handling of it should be able to
account for this.

It will require documentation to be clear that sorting methods should
take care not to leave anything incomplete if a closure throws; most
algorithms should be fine since they usually just test the closure
then swap two values afterwards (where necessary) so there’s nothing
really to interrupt, but anything that uses some kind of buffering may
need to be redesigned to ensure there’s a fallback to ensure no
elements are ever lost.

--
Dave


(Saagar Jha) #5

Might I add that leaving an array in an arbitrary and
implementation-dependent state is also surprising to users as well as not
very useful-to the user this is nothing more than a random permutation.

···

On Mon, Jun 6, 2016 at 5:31 PM Dave Abrahams via swift-evolution < swift-evolution@swift.org> wrote:

on Sun Jun 05 2016, Haravikk <swift-evolution@swift.org> wrote:

>> On 5 Jun 2016, at 19:14, Tim Vermeulen via swift-evolution < > swift-evolution@swift.org> wrote:
>>
>> Most standard library functions that take a closure allow that
>> closure to throw (and those functions are subsequently marked with
>> rethrows). sort and sorted are exceptions to this. I couldn’t find
>
>> this documented anywhere, but I assume this is because sorting can
>> happen in-place and it would be impossible to restore the array to
>> its original state without giving up performance. Correct me if I’m
>> wrong.
>>
>> I’d like to propose that we let sort rethrow anyways, and leave the
>> array in an intermediate state (where the elements are in an
>> arbitrary order) when an error is thrown. As long as this is
>> properly documented, this shouldn’t lead to any confusion. Best of
>> all, it would allow sorted to rethrow as well in which there is no
>> room for confusion at all because it doesn’t mutate any of the
>> user’s variables.
>
> This sounds reasonable; worst case with in-place sorting is that the
> collection was sorted in one order, and is only partially sorted in a
> new one, but the exception and your handling of it should be able to
> account for this.
>
> It will require documentation to be clear that sorting methods should
> take care not to leave anything incomplete if a closure throws; most
> algorithms should be fine since they usually just test the closure
> then swap two values afterwards (where necessary) so there’s nothing
> really to interrupt, but anything that uses some kind of buffering may
> need to be redesigned to ensure there’s a fallback to ensure no
> elements are ever lost.

Ensuring that no elements are ever lost is not a particularly useful
goal, and not a constraint to which I would want to hold the standard
library.

--
Dave

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

--
-Saagar Jha


(Dave Abrahams) #6

Might I add that leaving an array in an arbitrary and
implementation-dependent state is also surprising to users as well as not
very useful-to the user this is nothing more than a random permutation.

True, but the cost of being able to restore the original ordering, when
that restoration may not be needed at all, is prohibitive. It's often
the case that the caller will be throwing away the partially-modified
original when an error is thrown.

···

on Mon Jun 06 2016, Saagar Jha <saagarjha28-AT-gmail.com> wrote:

On Mon, Jun 6, 2016 at 5:31 PM Dave Abrahams via swift-evolution < > swift-evolution@swift.org> wrote:

on Sun Jun 05 2016, Haravikk <swift-evolution@swift.org> wrote:

>> On 5 Jun 2016, at 19:14, Tim Vermeulen via swift-evolution < >> swift-evolution@swift.org> wrote:
>>
>> Most standard library functions that take a closure allow that
>> closure to throw (and those functions are subsequently marked with
>> rethrows). sort and sorted are exceptions to this. I couldn’t find
>
>> this documented anywhere, but I assume this is because sorting can
>> happen in-place and it would be impossible to restore the array to
>> its original state without giving up performance. Correct me if I’m
>> wrong.
>>
>> I’d like to propose that we let sort rethrow anyways, and leave the
>> array in an intermediate state (where the elements are in an
>> arbitrary order) when an error is thrown. As long as this is
>> properly documented, this shouldn’t lead to any confusion. Best of
>> all, it would allow sorted to rethrow as well in which there is no
>> room for confusion at all because it doesn’t mutate any of the
>> user’s variables.
>
> This sounds reasonable; worst case with in-place sorting is that the
> collection was sorted in one order, and is only partially sorted in a
> new one, but the exception and your handling of it should be able to
> account for this.
>
> It will require documentation to be clear that sorting methods should
> take care not to leave anything incomplete if a closure throws; most
> algorithms should be fine since they usually just test the closure
> then swap two values afterwards (where necessary) so there’s nothing
> really to interrupt, but anything that uses some kind of buffering may
> need to be redesigned to ensure there’s a fallback to ensure no
> elements are ever lost.

Ensuring that no elements are ever lost is not a particularly useful
goal, and not a constraint to which I would want to hold the standard
library.

--
Dave

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

--
Dave


(Saagar Jha) #7

Exactly. While rethrows for sort make sense, since there is no user
variable modification, sortInPlace either needs to revert the array (which
is potentially expensive) or leave it in an arbitrary state, neither of
which are good choices. I can’t seem to find any mutating function that
rethrows, and I think it’s for precisely this reason.

···

On Tue, Jun 7, 2016 at 10:20 AM Dave Abrahams <dabrahams@apple.com> wrote:

on Mon Jun 06 2016, Saagar Jha <saagarjha28-AT-gmail.com> wrote:

> Might I add that leaving an array in an arbitrary and
> implementation-dependent state is also surprising to users as well as not
> very useful-to the user this is nothing more than a random permutation.

True, but the cost of being able to restore the original ordering, when
that restoration may not be needed at all, is prohibitive. It's often
the case that the caller will be throwing away the partially-modified
original when an error is thrown.

> On Mon, Jun 6, 2016 at 5:31 PM Dave Abrahams via swift-evolution < > > swift-evolution@swift.org> wrote:
>
>>
>> on Sun Jun 05 2016, Haravikk <swift-evolution@swift.org> wrote:
>>
>> >> On 5 Jun 2016, at 19:14, Tim Vermeulen via swift-evolution < > >> swift-evolution@swift.org> wrote:
>> >>
>> >> Most standard library functions that take a closure allow that
>> >> closure to throw (and those functions are subsequently marked with
>> >> rethrows). sort and sorted are exceptions to this. I couldn’t find
>> >
>> >> this documented anywhere, but I assume this is because sorting can
>> >> happen in-place and it would be impossible to restore the array to
>> >> its original state without giving up performance. Correct me if I’m
>> >> wrong.
>> >>
>> >> I’d like to propose that we let sort rethrow anyways, and leave the
>> >> array in an intermediate state (where the elements are in an
>> >> arbitrary order) when an error is thrown. As long as this is
>> >> properly documented, this shouldn’t lead to any confusion. Best of
>> >> all, it would allow sorted to rethrow as well in which there is no
>> >> room for confusion at all because it doesn’t mutate any of the
>> >> user’s variables.
>> >
>> > This sounds reasonable; worst case with in-place sorting is that the
>> > collection was sorted in one order, and is only partially sorted in a
>> > new one, but the exception and your handling of it should be able to
>> > account for this.
>> >
>> > It will require documentation to be clear that sorting methods should
>> > take care not to leave anything incomplete if a closure throws; most
>> > algorithms should be fine since they usually just test the closure
>> > then swap two values afterwards (where necessary) so there’s nothing
>> > really to interrupt, but anything that uses some kind of buffering may
>> > need to be redesigned to ensure there’s a fallback to ensure no
>> > elements are ever lost.
>>
>> Ensuring that no elements are ever lost is not a particularly useful
>> goal, and not a constraint to which I would want to hold the standard
>> library.
>>
>> --
>> Dave
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>

--
Dave

--
-Saagar Jha


(Tim Vermeulen) #8

True, but the cost of being able to restore the original ordering, when
that restoration may not be needed at all, is prohibitive.

What about simply restoring the elements, in no particular order? This seems like an easy enough task, and I don’t think it requires the sorting algorithm to allocate any extra memory (in case no error is thrown, at least).

···

on Mon Jun 06 2016, Saagar Jha<saagarjha28-AT-gmail.com>wrote:

> Might I add that leaving an array in an arbitrary and
> implementation-dependent state is also surprising to users as well as not
> very useful-to the user this is nothing more than a random permutation.
True, but the cost of being able to restore the original ordering, when
that restoration may not be needed at all, is prohibitive. It's often
the case that the caller will be throwing away the partially-modified
original when an error is thrown.

> On Mon, Jun 6, 2016 at 5:31 PM Dave Abrahams via swift-evolution< > > swift-evolution@swift.org>wrote:
>
> >
> > on Sun Jun 05 2016, Haravikk<swift-evolution@swift.org>wrote:
> >
> > > > On 5 Jun 2016, at 19:14, Tim Vermeulen via swift-evolution< > > > swift-evolution@swift.org>wrote:
> > > >
> > > > Most standard library functions that take a closure allow that
> > > > closure to throw (and those functions are subsequently marked with
> > > > rethrows). sort and sorted are exceptions to this. I couldn’t find
> > >
> > > > this documented anywhere, but I assume this is because sorting can
> > > > happen in-place and it would be impossible to restore the array to
> > > > its original state without giving up performance. Correct me if I’m
> > > > wrong.
> > > >
> > > > I’d like to propose that we let sort rethrow anyways, and leave the
> > > > array in an intermediate state (where the elements are in an
> > > > arbitrary order) when an error is thrown. As long as this is
> > > > properly documented, this shouldn’t lead to any confusion. Best of
> > > > all, it would allow sorted to rethrow as well in which there is no
> > > > room for confusion at all because it doesn’t mutate any of the
> > > > user’s variables.
> > >
> > > This sounds reasonable; worst case with in-place sorting is that the
> > > collection was sorted in one order, and is only partially sorted in a
> > > new one, but the exception and your handling of it should be able to
> > > account for this.
> > >
> > > It will require documentation to be clear that sorting methods should
> > > take care not to leave anything incomplete if a closure throws; most
> > > algorithms should be fine since they usually just test the closure
> > > then swap two values afterwards (where necessary) so there’s nothing
> > > really to interrupt, but anything that uses some kind of buffering may
> > > need to be redesigned to ensure there’s a fallback to ensure no
> > > elements are ever lost.
> >
> > Ensuring that no elements are ever lost is not a particularly useful
> > goal, and not a constraint to which I would want to hold the standard
> > library.
> >
> > --
> > Dave
> >
> > _______________________________________________
> > swift-evolution mailing list
> > swift-evolution@swift.org
> > https://lists.swift.org/mailman/listinfo/swift-evolution
--
Dave


(Dave Abrahams) #9

Exactly. While rethrows for sort make sense, since there is no user
variable modification, sortInPlace either needs to revert the array (which
is potentially expensive) or leave it in an arbitrary state, neither of
which are good choices. I can’t seem to find any mutating function that
rethrows, and I think it’s for precisely this reason.

Please trust me when I tell you that that is not the reason.

···

on Tue Jun 07 2016, Saagar Jha <saagarjha28-AT-gmail.com> wrote:

On Tue, Jun 7, 2016 at 10:20 AM Dave Abrahams <dabrahams@apple.com> wrote:

on Mon Jun 06 2016, Saagar Jha <saagarjha28-AT-gmail.com> wrote:

> Might I add that leaving an array in an arbitrary and
> implementation-dependent state is also surprising to users as well as not
> very useful-to the user this is nothing more than a random permutation.

True, but the cost of being able to restore the original ordering, when
that restoration may not be needed at all, is prohibitive. It's often
the case that the caller will be throwing away the partially-modified
original when an error is thrown.

> On Mon, Jun 6, 2016 at 5:31 PM Dave Abrahams via swift-evolution < >> > swift-evolution@swift.org> wrote:
>
>>
>> on Sun Jun 05 2016, Haravikk <swift-evolution@swift.org> wrote:
>>
>> >> On 5 Jun 2016, at 19:14, Tim Vermeulen via swift-evolution < >> >> swift-evolution@swift.org> wrote:
>> >>
>> >> Most standard library functions that take a closure allow that
>> >> closure to throw (and those functions are subsequently marked with
>> >> rethrows). sort and sorted are exceptions to this. I couldn’t find
>> >
>> >> this documented anywhere, but I assume this is because sorting can
>> >> happen in-place and it would be impossible to restore the array to
>> >> its original state without giving up performance. Correct me if I’m
>> >> wrong.
>> >>
>> >> I’d like to propose that we let sort rethrow anyways, and leave the
>> >> array in an intermediate state (where the elements are in an
>> >> arbitrary order) when an error is thrown. As long as this is
>> >> properly documented, this shouldn’t lead to any confusion. Best of
>> >> all, it would allow sorted to rethrow as well in which there is no
>> >> room for confusion at all because it doesn’t mutate any of the
>> >> user’s variables.
>> >
>> > This sounds reasonable; worst case with in-place sorting is that the
>> > collection was sorted in one order, and is only partially sorted in a
>> > new one, but the exception and your handling of it should be able to
>> > account for this.
>> >
>> > It will require documentation to be clear that sorting methods should
>> > take care not to leave anything incomplete if a closure throws; most
>> > algorithms should be fine since they usually just test the closure
>> > then swap two values afterwards (where necessary) so there’s nothing
>> > really to interrupt, but anything that uses some kind of buffering may
>> > need to be redesigned to ensure there’s a fallback to ensure no
>> > elements are ever lost.
>>
>> Ensuring that no elements are ever lost is not a particularly useful
>> goal, and not a constraint to which I would want to hold the standard
>> library.
>>
>> --
>> Dave
>>
>> _______________________________________________
>> swift-evolution mailing list
>> swift-evolution@swift.org
>> https://lists.swift.org/mailman/listinfo/swift-evolution
>>

--
Dave

--
-Dave


(Chris Lattner) #10

What is the example that motivates this? Is there a widely used comparison function that throws?

-Chris

···

On Jun 7, 2016, at 12:07 PM, Tim Vermeulen via swift-evolution <swift-evolution@swift.org> wrote:

True, but the cost of being able to restore the original ordering, when
that restoration may not be needed at all, is prohibitive.

What about simply restoring the elements, in no particular order? This seems like an easy enough task, and I don’t think it requires the sorting algorithm to allocate any extra memory (in case no error is thrown, at least).


(Brent Royal-Gordon) #11

Is there a widely used comparison function that throws?

Any comparison function that examines external data related to the instance:

* Sorting filenames by the data in the corresponding files
* Instances backed by a database where actually loading the data could fail
* Etc.

···

--
Brent Royal-Gordon
Architechies


(Chris Lattner) #12

Ok, instead of using rethrows, would it be a better overall design be to define two overloads, one that takes a throwing closure and one that doesn’t? This allows the throw-supporting implementation to be slower without punishing the normal case..

-Chris

···

On Jun 8, 2016, at 7:52 AM, Brent Royal-Gordon <brent@architechies.com> wrote:

Is there a widely used comparison function that throws?

Any comparison function that examines external data related to the instance:

* Sorting filenames by the data in the corresponding files
* Instances backed by a database where actually loading the data could fail
* Etc.


(Dave Abrahams) #13

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.

···

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

Is there a widely used comparison function that throws?

Any comparison function that examines external data related to the instance:

* Sorting filenames by the data in the corresponding files

* Instances backed by a database where actually loading the data could
  fail

* Etc.

--
Dave


(Tim Vermeulen) #14

Not that I know of. It’s rather an attempt at making the standard library more consistent. The main reason being that the `isOrderedBefore` parameter in `max(isOrderedBefore:)` has the exact same type (`@noescape (Iterator.Element, Iterator.Element) -> Bool`) except that it is allowed to throw. I know that there’s no good reason to not let `max` rethrow, but for the sake of consistency, I figured it would make sense and it would be feasible to let `sort` and `sorted` also rethrow.

···

> On Jun 7, 2016, at 12:07 PM, Tim Vermeulen via swift-evolution<swift-evolution@swift.org>wrote:
>
> > True, but the cost of being able to restore the original ordering, when
> > that restoration may not be needed at all, is prohibitive.
>
> What about simply restoring the elements, in no particular order? This seems like an easy enough task, and I don’t think it requires the sorting algorithm to allocate any extra memory (in case no error is thrown, at least).
What is the example that motivates this? Is there a widely used comparison function that throws?

-Chris


(Dave Abrahams) #15

There is *no reason* to do this.

* Most sorting algorithms can be written so that even if the comparison
  throws, no elements are lost

* Even if elements were lost—though it might indeed be surprising—it's
  not actually a problem we should solve, especially not by penalizing
  performance. It's *very* unlikely that a partially scrambled
  collection is of any use to the caller in real code.

* Giving commit-or-rollback semantics for every operation is not
  something we should do by penalizing performance. Commit-or-rollback
  does not compose, and therefore ends up uselessly penalizing
  performance in compositions.

···

on Wed Jun 08 2016, Chris Lattner <clattner-AT-apple.com> wrote:

On Jun 8, 2016, at 7:52 AM, Brent Royal-Gordon <brent@architechies.com> wrote:

Is there a widely used comparison function that throws?

Any comparison function that examines external data related to the instance:

* Sorting filenames by the data in the corresponding files
* Instances backed by a database where actually loading the data could fail
* Etc.

Ok, instead of using rethrows, would it be a better overall design be
to define two overloads, one that takes a throwing closure and one
that doesn’t? This allows the throw-supporting implementation to be
slower without punishing the normal case..

--
Dave


(Christopher Kornher) #16

+1 This is straightforward and self-documenting.

···

On Jun 8, 2016, at 11:21 AM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

On Jun 8, 2016, at 7:52 AM, Brent Royal-Gordon <brent@architechies.com> wrote:

Is there a widely used comparison function that throws?

Any comparison function that examines external data related to the instance:

* Sorting filenames by the data in the corresponding files
* Instances backed by a database where actually loading the data could fail
* Etc.

Ok, instead of using rethrows, would it be a better overall design be to define two overloads, one that takes a throwing closure and one that doesn’t? This allows the throw-supporting implementation to be slower without punishing the normal case..

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


(Tim Vermeulen) #17

Of course, on performance of the normal case should never be compromised. So if making two overloads is the only way to ensure that, then that’s what it takes. But will the performance of the normal case really suffer if we only require a sorting algorithm to restore the array to an arbitrary permutation of the original array, in case of an error?

If the consensus is that the original order of the array should be restored, then the normal case would obviously suffer from it. But I think just making sure no elements are lost is way more important than ensuring that the order is preserved. After all, changing the order is what a sorting algorithm does, so the original order is probably not crucial. But if the elements might be lost, people might be encouraged to make a back-up of the array before sorting it, in case an error is thrown.

···

> On Jun 8, 2016, at 7:52 AM, Brent Royal-Gordon<brent@architechies.com>wrote:
>
> > Is there a widely used comparison function that throws?
>
> Any comparison function that examines external data related to the instance:
>
> * Sorting filenames by the data in the corresponding files
> * Instances backed by a database where actually loading the data could fail
> * Etc.
Ok, instead of using rethrows, would it be a better overall design be to define two overloads, one that takes a throwing closure and one that doesn’t? This allows the throw-supporting implementation to be slower without punishing the normal case..

-Chris


(Brent Royal-Gordon) #18

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


(L Mihalkovic) #19

Is there a widely used comparison function that throws?

Any comparison function that examines external data related to the instance:

* Sorting filenames by the data in the corresponding files
* Instances backed by a database where actually loading the data could fail
* Etc.

Ok, instead of using rethrows, would it be a better overall design be to define two overloads, one that takes a throwing closure and one that doesn’t? This allows the throw-supporting implementation to be slower without punishing the normal case..

Smilar solution to what java did.

···

On Jun 8, 2016, at 7:21 PM, Chris Lattner via swift-evolution <swift-evolution@swift.org> wrote:

On Jun 8, 2016, at 7:52 AM, Brent Royal-Gordon <brent@architechies.com> wrote:

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


(Jordan Rose) #20

FWIW Dave gave me most of the same feedback in the discussion on the proof-of-concept pull request: https://github.com/apple/swift/pull/1527#discussion_r60811569

Jordan

···

On Jun 8, 2016, at 11:06, Dave Abrahams via swift-evolution <swift-evolution@swift.org> wrote:

on Wed Jun 08 2016, Chris Lattner <clattner-AT-apple.com> wrote:

On Jun 8, 2016, at 7:52 AM, Brent Royal-Gordon <brent@architechies.com> wrote:

Is there a widely used comparison function that throws?

Any comparison function that examines external data related to the instance:

* Sorting filenames by the data in the corresponding files
* Instances backed by a database where actually loading the data could fail
* Etc.

Ok, instead of using rethrows, would it be a better overall design be
to define two overloads, one that takes a throwing closure and one
that doesn’t? This allows the throw-supporting implementation to be
slower without punishing the normal case..

There is *no reason* to do this.

* Most sorting algorithms can be written so that even if the comparison
throws, no elements are lost

* Even if elements were lost—though it might indeed be surprising—it's
not actually a problem we should solve, especially not by penalizing
performance. It's *very* unlikely that a partially scrambled
collection is of any use to the caller in real code.

* Giving commit-or-rollback semantics for every operation is not
something we should do by penalizing performance. Commit-or-rollback
does not compose, and therefore ends up uselessly penalizing
performance in compositions.