Why can't I use `not` in generic where clause?

I am implementing an intrusive binary search tree. I wanted to make this as generic as possible, and wanted to use the same implementation for a dictionary type and a set. I thought I could do something like this:

public extension TreapMap where ValueType == Void {
    mutating func insert(_ key: KeyType) -> Bool {
        let node = Node(key: key, value: ())
        return insert(node)
    }
}

public extension TreapMap where ValueType != Void {
    mutating func insert(key: KeyType, value: ValueType) -> Bool {
        let node = Node(key: key, value: value)
        return insert(node)
    }
}

and then later do something like this:

typealias TreapSet<K: Comparable> = TreapMap<K, Void>

But the compiler tells me that it expects : or == to indicate conformance or same-type requirements. Why can't I do !=? Would this be a reasonable feature request?

It is unclear to me what the semantics of this requirement should be. What would it imply about the ValueType type parameter inside the body of this extension? Also, how do you check the requirement at the call site? If ValueType is substituted with some other unconstrained generic parameter, do you reject the substitution on the grounds that you cannot statically prove the type of the other generic parameter will never be Void?

1 Like

I simply want to do what std::enable_if (or now a concept) in C++ can do.

ValueType is statically known. The struct definition is something like this:

struct TreapMap<K: Comparable, V> {
  typealias KeyType = K
  typealias ValueType = V
  ...
}

So I want this extension to be available if ValueType is anything else than Void. High level, this would allow my to have two different insert functions and only one of them is available at any point in time.

Or am I missing some corner-case where ValueType would only be known at runtime?

Swift generics are not always eagerly instantiated, unlike C++ templates, since they can be called from other modules separately compiled from the definition. You can also invoke generics using the dynamic type out of any Protocol types and things like that, so generic parameters are indeed sometimes only known at runtime. In your example, it's harmless to leave insert(key:value:) available for Void value types, and to me it even seems desirable: if you're writing a generic function that works for any ValueType, that is the insert function you'd have to use.

3 Likes

I guess I might not quite understand how Swift's type system is implemented... So if I have something like this:

extension Foo where Element: Comparable {
  ...
}

Then whatever is in this extension will only be available if Element implements Comparable. So what happens if I have something like any Protocol? What will the compiler do then? Not allow my to use the extension? Or allow me to use it but potentially generate a runtime error?

And still my question remains (independent of my specific example): would it make sense to request a feature where I can do where Type != SomeType? Maybe I am too confused here, but it seems whatever the compiler is doing to proof the positive case it could also do for the negative case, no?

Swift won't let you pass an any Protocol directly, unless Protocol happens to require Comparable, but you could for instance dynamically cast foo as? Comparable to dynamically determine whether the value is Comparable, and if it is, invoke methods that require Comparable on the result of the cast.

Negative constraints are fundamentally of limited use because they don't usually enable the generic function to do anything new; knowing that a value isn't one particular type doesn't unlock new capabilities in the way that knowing it is a specific type or does conform to a specific protocol do. They also are difficult to statically propagate through generics; as Slava noted, if you have a function that requires T: P, T != Foo, then you can't call that function from any other function that only requires T: P, since that latter function might be working with a Foo. Negative constraints would also create logical complexities when combining protocols, since it would be possible to come up with a situation where one protocol P requires Self.Foo == Bar and another protocol Q requires Self.Foo != Bar, and now the composition P & Q is impossible to satisfy.

5 Likes

I see, I think this makes sense. I think I am too much used by templates (and they're not the same as generics). I think what I want is specialization. For example, when implementing Sequence I want my map to have Element = (KeyType, ValueType) unless if the value type is Void in which case I want Element = KeyType.

But I think the proper way to do these kind of things in swift would be to have different protocols with extensions that implement most of the logic and than have different structs for a dictionary and a set type.

I am not unhappy about this, since this seems to be actual proper typing and not like in C++ where we basically get a code generator and std::vector<signed int> is a completely different type from std::vector<unsigned>...

The only counter-example might be AnyObject though? If I know something is a struct, would this allow me to do things that I wouldn't be able to do with classes or actors? Though I might be wrong here, because every example I could think of Sendable would be the right thing to check for...

Have you considered not making your set an alias of a map with void values? A set is not a map and I think you are fighting the language a bit by trying to pretend it is. I would make the set a new type that uses the map as a backing store.