After reviewing the code of stdlib I found no one actually implements _customContainsEquatableElement:
1. Its default implementation in `SequenceType` just returns nil.
2. The implementation in `Set` delegates to `contains` which is bad because it reverses their relationship: the default implementation of `contains` in `SequenceType` delegates to `_customContainsEquatableElement`.
3. In all other place it just delegates to another `SequenceType`.
So no one is doing real work.
If the current _customContainsEquatableElement is only a relic I suggest we remove it and clean up related code.
FWIW, once we have conditional protocol conformance (`extension ... : Proto where ...`), and if we get rid of the circular protocol inheritance limitation (two protocols that inherit from each other, which should in theory be fine), then we can say something like
This way the method can actually be overridden directly without requiring any hacks like _customContainsEquatableElement.
We could work around the circular protocol inheritance thing by declaring a `typealias _Element : Equatable` in EquatableSequenceType instead of having the inheritance, and then just set `typealias _Element = Self.Generator.Element` in the protocol extension on SequenceType, but that does in theory let implementing types actually change the type of the contains() method parameter by overriding the typealias, which is a bit weird. Alternatively, we could work around it by allowing you to say `extension Any : EquatableSequenceType where Self : SequenceType { ... }` and having that essentially extend every concrete type that conforms to SequenceType, which means SequenceType itself doesn't conform to EquatableSequenceType and therefore there's no circular protocol inheritance, but I'm not sure if this is actually an approach we want to take (although this is precisely what Rust does and it works for them).
-Kevin Ballard
···
On Wed, Dec 30, 2015, at 10:34 AM, Ling Wang via swift-dev wrote:
After reviewing the code of stdlib I found no one actually implements _customContainsEquatableElement:
1. Its default implementation in `SequenceType` just returns nil.
2. The implementation in `Set` delegates to `contains` which is bad because it reverses their relationship: the default implementation of `contains` in `SequenceType` delegates to `_customContainsEquatableElement`.
3. In all other place it just delegates to another `SequenceType`.
So no one is doing real work.
If the current _customContainsEquatableElement is only a relic I suggest we remove it and clean up related code.
_______________________________________________
swift-dev mailing list
swift-dev@swift.org https://lists.swift.org/mailman/listinfo/swift-dev
It is not a relic. It allows the contains() method to perform dynamic
dispatch in case the container knows something extra about the
elements.
Consider the case when you have a Set typed as a plain Sequence or a
Collection. In that case, you won't be able to call the custom
Set.contains() method, the overload resolution will only see the
protocol extension. This extra entry point,
_customContainsEquatableElement, allows us to perform dynamic dispatch
and use the fast Set implementation if it is available.
Dmitri
···
On Wed, Dec 30, 2015 at 8:34 PM, Ling Wang via swift-dev <swift-dev@swift.org> wrote:
After reviewing the code of stdlib I found no one actually implements _customContainsEquatableElement:
1. Its default implementation in `SequenceType` just returns nil.
2. The implementation in `Set` delegates to `contains` which is bad because it reverses their relationship: the default implementation of `contains` in `SequenceType` delegates to `_customContainsEquatableElement`.
3. In all other place it just delegates to another `SequenceType`.
So no one is doing real work.
If the current _customContainsEquatableElement is only a relic I suggest we remove it and clean up related code.
Got it. `contains` is only declared in extension. Interesting workaround. Thanks.
···
On Dec 30, 2015, at 4:45 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Wed, Dec 30, 2015 at 8:34 PM, Ling Wang via swift-dev > <swift-dev@swift.org> wrote:
After reviewing the code of stdlib I found no one actually implements _customContainsEquatableElement:
1. Its default implementation in `SequenceType` just returns nil.
2. The implementation in `Set` delegates to `contains` which is bad because it reverses their relationship: the default implementation of `contains` in `SequenceType` delegates to `_customContainsEquatableElement`.
3. In all other place it just delegates to another `SequenceType`.
So no one is doing real work.
If the current _customContainsEquatableElement is only a relic I suggest we remove it and clean up related code.
It is not a relic. It allows the contains() method to perform dynamic
dispatch in case the container knows something extra about the
elements.
Consider the case when you have a Set typed as a plain Sequence or a
Collection. In that case, you won't be able to call the custom
Set.contains() method, the overload resolution will only see the
protocol extension. This extra entry point,
_customContainsEquatableElement, allows us to perform dynamic dispatch
and use the fast Set implementation if it is available.
FWIW, once we have conditional protocol conformance (`extension ... : Proto where ...`), and if we get rid of the circular protocol inheritance limitation (two protocols that inherit from each other, which should in theory be fine), then we can say something like
This way the method can actually be overridden directly without requiring any hacks like _customContainsEquatableElement.
We could work around the circular protocol inheritance thing by declaring a `typealias _Element : Equatable` in EquatableSequenceType instead of having the inheritance, and then just set `typealias _Element = Self.Generator.Element` in the protocol extension on SequenceType, but that does in theory let implementing types actually change the type of the contains() method parameter by overriding the typealias, which is a bit weird.
Tricks like this also usually break generic code because it can no longer count on the usual relationships between types.
Alternatively, we could work around it by allowing you to say `extension Any : EquatableSequenceType where Self : SequenceType { ... }` and having that essentially extend every concrete type that conforms to SequenceType, which means SequenceType itself doesn't conform to EquatableSequenceType and therefore there's no circular protocol inheritance, but I'm not sure if this is actually an approach we want to take (although this is precisely what Rust does and it works for them).
I don’t want to create stdlib churn working around the lack of generics features that we expect to have for the next release. We should just wait for the generics system to be ready.
-Dave
···
On Dec 30, 2015, at 4:50 PM, Kevin Ballard via swift-dev <swift-dev@swift.org> wrote:
Following the previous discussion do you think this is a good patch:
// O(1) implementation of `contains()` for ranges of comparable elements.
extension Range where Element: Comparable { @_transparent @warn_unused_result
func _customContainsEquatableElement(
element: Generator.Element
) -> Bool? {
return element >= self.startIndex && element < self.endIndex
}
}
···
On Dec 30, 2015, at 6:42 PM, Ling Wang <an00na@gmail.com> wrote:
Got it. `contains` is only declared in extension. Interesting workaround. Thanks.
On Dec 30, 2015, at 4:45 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Wed, Dec 30, 2015 at 8:34 PM, Ling Wang via swift-dev >> <swift-dev@swift.org> wrote:
After reviewing the code of stdlib I found no one actually implements _customContainsEquatableElement:
1. Its default implementation in `SequenceType` just returns nil.
2. The implementation in `Set` delegates to `contains` which is bad because it reverses their relationship: the default implementation of `contains` in `SequenceType` delegates to `_customContainsEquatableElement`.
3. In all other place it just delegates to another `SequenceType`.
So no one is doing real work.
If the current _customContainsEquatableElement is only a relic I suggest we remove it and clean up related code.
It is not a relic. It allows the contains() method to perform dynamic
dispatch in case the container knows something extra about the
elements.
Consider the case when you have a Set typed as a plain Sequence or a
Collection. In that case, you won't be able to call the custom
Set.contains() method, the overload resolution will only see the
protocol extension. This extra entry point,
_customContainsEquatableElement, allows us to perform dynamic dispatch
and use the fast Set implementation if it is available.
This suggestion was not meant as a workaround for the genetics limitation but for the following problem:
protocol Foo : Bar {}
protocol Bar : Foo {}
This throws an error about circular protocol inheritance.
-Kevin
···
On Dec 31, 2015, at 1:07 AM, Dave Abrahams <dabrahams@apple.com> wrote:
Alternatively, we could work around it by allowing you to say `extension Any : EquatableSequenceType where Self : SequenceType { ... }` and having that essentially extend every concrete type that conforms to SequenceType, which means SequenceType itself doesn't conform to EquatableSequenceType and therefore there's no circular protocol inheritance, but I'm not sure if this is actually an approach we want to take (although this is precisely what Rust does and it works for them).
I don’t want to create stdlib churn working around the lack of generics features that we expect to have for the next release. We should just wait for the generics system to be ready.
Yes, I think it is good -- this is exactly the use case for this
method, except that @_transparent should be dropped, and the comment
is duplicating the code, so it should be dropped, too. The change
also needs a simple test that checks that calling .contains() on a
suitable Range should dispatch to this method (you can detect that by
using MinimalComparableValue and supplying it a custom lessImpl that
counts the number of invocations).
Dmitri
···
On Thu, Dec 31, 2015 at 7:05 PM, Ling Wang <an00na@gmail.com> wrote:
Following the previous discussion do you think this is a good patch:
// O(1) implementation of `contains()` for ranges of comparable elements.
extension Range where Element: Comparable { @_transparent @warn_unused_result
func _customContainsEquatableElement(
element: Generator.Element
) -> Bool? {
return element >= self.startIndex && element < self.endIndex
}
}
On Dec 30, 2015, at 6:42 PM, Ling Wang <an00na@gmail.com> wrote:
Got it. `contains` is only declared in extension. Interesting workaround. Thanks.
On Dec 30, 2015, at 4:45 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Wed, Dec 30, 2015 at 8:34 PM, Ling Wang via swift-dev >>> <swift-dev@swift.org> wrote:
After reviewing the code of stdlib I found no one actually implements _customContainsEquatableElement:
1. Its default implementation in `SequenceType` just returns nil.
2. The implementation in `Set` delegates to `contains` which is bad because it reverses their relationship: the default implementation of `contains` in `SequenceType` delegates to `_customContainsEquatableElement`.
3. In all other place it just delegates to another `SequenceType`.
So no one is doing real work.
If the current _customContainsEquatableElement is only a relic I suggest we remove it and clean up related code.
It is not a relic. It allows the contains() method to perform dynamic
dispatch in case the container knows something extra about the
elements.
Consider the case when you have a Set typed as a plain Sequence or a
Collection. In that case, you won't be able to call the custom
Set.contains() method, the overload resolution will only see the
protocol extension. This extra entry point,
_customContainsEquatableElement, allows us to perform dynamic dispatch
and use the fast Set implementation if it is available.
On Dec 31, 2015, at 1:11 AM, Kevin Ballard <kevin@sb.org> wrote:
On Dec 31, 2015, at 1:07 AM, Dave Abrahams <dabrahams@apple.com> wrote:
Alternatively, we could work around it by allowing you to say `extension Any : EquatableSequenceType where Self : SequenceType { ... }` and having that essentially extend every concrete type that conforms to SequenceType, which means SequenceType itself doesn't conform to EquatableSequenceType and therefore there's no circular protocol inheritance, but I'm not sure if this is actually an approach we want to take (although this is precisely what Rust does and it works for them).
I don’t want to create stdlib churn working around the lack of generics features that we expect to have for the next release. We should just wait for the generics system to be ready.
This suggestion was not meant as a workaround for the genetics limitation but for the following problem:
protocol Foo : Bar {}
protocol Bar : Foo {}
This throws an error about circular protocol inheritance.
That is one of the generics limitations I’m referring to.
Do you mean something like this in validation-test/stdlib/SequenceType.swift.gyb:
SequenceTypeTests.test("Range<Element>.contains/WhereElementIsComparable/dispatch") {
MinimalComparableValue.timesLessWasCalled = 0
let start = 0
let end = 10
let range = Range(start: MinimalComparableValue(start), end: MinimalComparableValue(end))
let count = 20
for test in 0...count {
expectEqual(
test >= start && test < end,
range.contains(MinimalComparableValue(test)))
}
expectEqual(
count * 2, MinimalComparableValue.timesLessWasCalled)
}
There is one issue. MinimalComparableValue doesn’t conform to ForwardIndexType. I’m not sure it is proper for me to add this conformance in an extension because the definition of MinimalComparableValue is “A type that conforms only to `Equatable` and `Comparable`”.
What’s your suggestion?
···
On Dec 31, 2015, at 11:21 AM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
Yes, I think it is good -- this is exactly the use case for this
method, except that @_transparent should be dropped, and the comment
is duplicating the code, so it should be dropped, too. The change
also needs a simple test that checks that calling .contains() on a
suitable Range should dispatch to this method (you can detect that by
using MinimalComparableValue and supplying it a custom lessImpl that
counts the number of invocations).
Dmitri
On Thu, Dec 31, 2015 at 7:05 PM, Ling Wang <an00na@gmail.com> wrote:
Following the previous discussion do you think this is a good patch:
// O(1) implementation of `contains()` for ranges of comparable elements.
extension Range where Element: Comparable { @_transparent @warn_unused_result
func _customContainsEquatableElement(
element: Generator.Element
) -> Bool? {
return element >= self.startIndex && element < self.endIndex
}
}
On Dec 30, 2015, at 6:42 PM, Ling Wang <an00na@gmail.com> wrote:
Got it. `contains` is only declared in extension. Interesting workaround. Thanks.
On Dec 30, 2015, at 4:45 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Wed, Dec 30, 2015 at 8:34 PM, Ling Wang via swift-dev >>>> <swift-dev@swift.org> wrote:
After reviewing the code of stdlib I found no one actually implements _customContainsEquatableElement:
1. Its default implementation in `SequenceType` just returns nil.
2. The implementation in `Set` delegates to `contains` which is bad because it reverses their relationship: the default implementation of `contains` in `SequenceType` delegates to `_customContainsEquatableElement`.
3. In all other place it just delegates to another `SequenceType`.
So no one is doing real work.
If the current _customContainsEquatableElement is only a relic I suggest we remove it and clean up related code.
It is not a relic. It allows the contains() method to perform dynamic
dispatch in case the container knows something extra about the
elements.
Consider the case when you have a Set typed as a plain Sequence or a
Collection. In that case, you won't be able to call the custom
Set.contains() method, the overload resolution will only see the
protocol extension. This extra entry point,
_customContainsEquatableElement, allows us to perform dynamic dispatch
and use the fast Set implementation if it is available.
Do you mean something like this in validation-test/stdlib/SequenceType.swift.gyb:
SequenceTypeTests.test("Range<Element>.contains/WhereElementIsComparable/dispatch") {
MinimalComparableValue.timesLessWasCalled = 0
let start = 0
let end = 10
let range = Range(start: MinimalComparableValue(start), end: MinimalComparableValue(end))
let count = 20
for test in 0...count {
expectEqual(
test >= start && test < end,
range.contains(MinimalComparableValue(test)))
}
expectEqual(
count * 2, MinimalComparableValue.timesLessWasCalled)
}
Yes, this would be good.
There is one issue. MinimalComparableValue doesn’t conform to ForwardIndexType. I’m not sure it is proper for me to add this conformance in an extension because the definition of MinimalComparableValue is “A type that conforms only to `Equatable` and `Comparable`”.
What’s your suggestion?
I think it would be appropriate to define a special type like
MinimalComparableValue just for this test since the requirements are
quite specific (Comparable + ForwardIndexType).
Dmitri
···
On Thu, Dec 31, 2015 at 10:06 PM, Ling Wang <an00na@gmail.com> wrote:
On Dec 31, 2015, at 3:49 PM, Dmitri Gribenko <gribozavr@gmail.com> wrote:
On Thu, Dec 31, 2015 at 10:06 PM, Ling Wang <an00na@gmail.com <mailto:an00na@gmail.com>> wrote:
Do you mean something like this in validation-test/stdlib/SequenceType.swift.gyb:
SequenceTypeTests.test("Range<Element>.contains/WhereElementIsComparable/dispatch") {
MinimalComparableValue.timesLessWasCalled = 0
let start = 0
let end = 10
let range = Range(start: MinimalComparableValue(start), end: MinimalComparableValue(end))
let count = 20
for test in 0...count {
expectEqual(
test >= start && test < end,
range.contains(MinimalComparableValue(test)))
}
expectEqual(
count * 2, MinimalComparableValue.timesLessWasCalled)
}
Yes, this would be good.
There is one issue. MinimalComparableValue doesn’t conform to ForwardIndexType. I’m not sure it is proper for me to add this conformance in an extension because the definition of MinimalComparableValue is “A type that conforms only to `Equatable` and `Comparable`”.
What’s your suggestion?
I think it would be appropriate to define a special type like
MinimalComparableValue just for this test since the requirements are
quite specific (Comparable + ForwardIndexType).