No compile-time guarantee

[tulushev]

The purpose of this package is to provide a provable, compile-time guarantee that it holds a non-empty collection. There are valid reasons why a compile-time guarantee is better than a runtime check.

Recently the implementation was changed to a runtime check without updating the readme, so now this one-liner crashes the library:

withUnsafeBytes(of: "") { $0.load(as: NonEmptyString.self).first }

All because the library no longer provides a compile-time guarantee as it claims. A previous implementation with head is resilient to those types of crashes.

I suggest either to revert the implementation or to change the description of the library.

[stephencelis]

We believe "compile-time guarantee" is still accurate with the exposed API, though we do understand invariants could leak into the system.

We evaluated the trade-offs before the change, and decided that for performance and correctness of the collection algorithms themselves, holding onto the whole collection was important.

Your one-liner still crashes in the earlier design, just earlier (at the time of loading, not the time of first). When unsafe APIs are involved, you throw a lot of these compile-time guarantees out the window.

We've talked about introducing a "phantom" element to force the memory layout:

struct NonEmpty<C: Collection> {
  var rawValue: C
  private let phantom: C.Element  // grabs any element of C at initialization
}

But haven't gotten around to exploring it, or found a material need to do so yet with the existing APIs.

[tulushev]

Your one-liner still crashes in the earlier design, just earlier (at the time of loading, not the time of first). When unsafe APIs are involved, you throw a lot of these compile-time guarantees out the window.

This is precisely where it should crash if it provides a compile-time guarantee. This crash means that it's impossible to construct this type in a wrong way, which is what the user of such a library would want.

Here is an example. Let's say we have a library that accepts a non-empty data type for one of it's APIs:

class Library {
  static func acceptValidInput(_ s: NonEmptyString) {}
}

With the current implementation of NonEmpty, we would be able to construct an empty version of this data type and pass it to the library. All the non-force-unwrapped APIs would work and the library would proceed to execute some effects, only crashing much later, when non-emptiness of the data type would be important.

let input = withUnsafeBytes(of: "") { $0.load(as: NonEmptyString.self)}

Library.acceptValidInput(input) // Library happily doing its effects, beleiving the type is non-empty

With a previous implementation, it would be impossible to construct this data type empty, and any input passed to the function would guarantee that it won't fail. Exactly what we want here.

let input = withUnsafeBytes(of: "") { $0.load(as: PreviousNonEmptyString.self)} // ❌ Crashes

Library.acceptValidInput(input) // Not executed

This is not a contrived example, our own public library accepts a non-empty key to work using a head implementation, and I'm evaluating if the new version of the API should use this library for it instead.

---

withUnsafeBytes and load are not contrived either, in another library we are interacting with a our own Swift code compiled to WASM. The interaction requires us passing pointers from Swift to WASM, and WASM loading the data types. Using the current implementation for that use case would be too dangerous.

I would even go as far as to say that the current implementation of NonEmpty is even worse than sprinkling guards around, as it lulls users into a false sense of security, guards would be a safer option.

We've talked about introducing a "phantom" element to force the memory layout:

This looks like an interesting compromize. It would guarantee that the data type holds some element, though, it doesn't prove the collection non-empty because the element is not proven to be a part of it.

---

I beleive correctness is more important than performance for users of this library. Users who value performance more than correctness would be satisfied with runtime checks anyway.

[stephencelis]

This looks like an interesting compromize. It would guarantee that the data type holds some element, though, it doesn't prove the collection non-empty because the element is not proven to be a part of it.

Right, it would only "prove" the NonEmpty is non-empty in that the structure contains at least one value. It makes no guarantees about that value's relation to the collection.

I beleive correctness is more important than performance for users of this library. Users who value performance more than correctness would be satisfied with runtime checks anyway.

Ideally we would be able to provide correctness and performance, so if the compromise is fruitful we'd love to hear about it. Note that one of the motivating reasons to wrap the entire base collection was for correctness. There were runtime bugs lurking in the previous implementation due to index shuffling, subsequence behaviors, default implementations leaking from the standard library, and more, all that were quite difficult to track down. While we have introduced potential invariants with the migration, we were able to eliminate a whole other class of bugs.

If memory correctness is more important for you, we recommend locking to the old version for now.

If you explore the compromise I mentioned earlier and it proves fruitful, please do share!

[kristofkalai]

Hi!

@stephencelis I would bring a slightly related point, since I don't like to mess with the details of memory allocation. I just read the readme, the first sentence of which says that the library "compile-time guarantees that a collection contains a value". Then I tried it and found that there is no guarantee. Simple example:

import SwiftUI
import NonEmpty

struct ContentView: View {
    var body: some View {
        Text("Hello, world!")
            .onAppear {
                let array = NonEmptyArray<Int>() // runtime crash
                let firstElement = array.first
                print(firstElement)
            }
    }
}

I understand what you are trying to say in this discussion, but then I think the readme should be updated and not state something that is obviously not true. In my example, the "compile-time guarantee" would not result in a runtime crash, but a build error. What do you think about it?