[pitch] One-sided Ranges


(Ben Cohen) #1

Hi Swift community,

Another proposal pitch. These operators were mentioned briefly in the String manifesto as prefixing/suffixing is very common with strings.

Online copy here: https://github.com/airspeedswift/swift-evolution/blob/71b819d30676c44234bac1aa999961fc5c39bcf3/proposals/NNNN-OneSidedRanges.md
One-sided Ranges

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Ben Cohen <https://github.com/airspeedswift>, Dave Abrahams <https://github.com/dabrahams>, Brent Royal-Gordon <https://github.com/brentdax>
Review Manager: TBD
Status: Awaiting review
Introduction

This proposal introduces the concept of a “one-sided” range, created via prefix/postfix versions of the existing range operators.

It also introduces a new protocol, RangeExpression, to simplify the creation of methods that take different kinds of ranges.

Motivation

It is common, given an index into a collection, to want a slice up to or from that index versus the start/end.

For example (assuming String is once more a Collection):

let s = "Hello, World!"
let i = s.index(where: ",")
let greeting = s[s.startIndex..<i]
When performing lots of slicing like this, the verbosity of repeating s.startIndex is tiresome to write and harmful to readability.

Swift 3’s solution to this is a family of methods:

let greeting = s.prefix(upTo: i)
let withComma = s.prefix(through: i)
let location = s.suffix(from: i)
The two very different-looking ways to perform a similar task is jarring. And as methods, the result cannot be used as an l-value.

A variant of the one-sided slicing syntax found in Python (i.e. s[i:]) is proposed to resolve this.

Proposed solution

Introduce a one-sided range syntax, where the “missing” side is inferred to be the start/end:

// half-open right-handed range
let greeting = s[..<i]
// closed right-handed range
let withComma = s[...i]
// left-handed range (no need for half-open variant)
let location = s[i...]
Additionally, when the index is a countable type, i... should form a Sequence that counts up from i indefinitely. This is useful in forming variants of Sequence.enumerated() when you either want them non-zero-based i.e. zip(1..., greeting), or want to flip the order i.e. zip(greeting, 0...).

This syntax would supercede the existing prefix and suffix operations that take indices, which will be deprecated in a later release. Note that the versions that take distances are not covered by this proposal, and would remain.

This will require the introduction of new range types (e.g. PartialRangeThrough). There are already multiple range types (e.g. ClosedRange, CountableHalfOpenRange), which require overloads to allow them to be used whereever a Range can be.

To unify these different range types, a new protocol, RangeExpression will be created and all ranges conformed to it. Existing overloads taking concrete types other than Range can then be replaced with a single generic method that takes a RangeExpression, converts it to a Range, and then forward the method on.

A generic version of ~= will also be implemented for all range expressions:

switch i {
case 9001...: print("It’s over NINE THOUSAAAAAAAND")
default: print("There's no way that can be right!")
}
The existing concrete overloads that take ranges other than Range will be deprecated in favor of generic ones that take a RangeExpression.

Detailed design

Add the following to the standard library:

(a fuller work-in-progress implementation can be found here: https://github.com/apple/swift/pull/8710)

NOTE: The following is subject to change depending on pending compiler features. Methods may actually be on underscored protocols, and then moved once recursive protocols are implemented. Types may be collapsed using conditional conformance. This should not matter from a usage perspective – users are not expected to use these types directly or override any of the behaviors in their own types. Any final implementation will follow the below in spirit if not in practice.

public protocol RangeExpression {
    associatedtype Bound: Comparable

    /// Returns `self` expressed as a range of indices within `collection`.
    ///
    /// -Parameter collection: The collection `self` should be
    /// relative to.
    ///
    /// -Returns: A `Range<Bound>` suitable for slicing `collection`.
    /// The return value is *not* guaranteed to be inside
    /// its bounds. Callers should apply the same preconditions
    /// to the return value as they would to a range provided
    /// directly by the user.
    func relative<C: _Indexable>(to collection: C) -> Range<Bound> where C.Index == Bound

    func contains(_ element: Bound) -> Bool
}

extension RangeExpression {
  public static func ~= (pattern: Self, value: Bound) -> Bool
}

prefix operator ..<
public struct PartialRangeUpTo<T: Comparable>: RangeExpression {
  public init(_ upperBound: T) { self.upperBound = upperBound }
  public let upperBound: T
}
extension Comparable {
  public static prefix func ..<(x: Self) -> PartialRangeUpTo<Self>
}

prefix operator ...
public struct PartialRangeThrough<T: Comparable>: RangeExpression {
  public init(_ upperBound: T)
  public let upperBound: T
}
extension Comparable {
  public static prefix func ...(x: Self) -> PartialRangeThrough<Self>
}

postfix operator ...
public struct PartialRangeFrom<T: Comparable>: RangeExpression {
  public init(_ lowerBound: T)
  public let lowerBound: T
}
extension Comparable {
  public static postfix func ...(x: Self) -> PartialRangeFrom<Self>
}

// The below relies on Conditional Conformance. Pending that feature,
// this may require an additional CountablePartialRangeFrom type temporarily.
extension PartialRangeFrom: Sequence
  where Index: _Strideable, Index.Stride : SignedInteger

extension Collection {
  public subscript<R: RangeExpression>(r: R) -> SubSequence
   where R.Bound == Index { get }
}
extension MutableCollection {
  public subscript<R: RangeExpression>(r: R) -> SubSequence
   where R.Bound == Index { get set }
}
  
extension RangeReplaceableColleciton {
  public mutating func replaceSubrange<C: Collection, R: RangeExpression>(
    _ subrange: ${Range}<Index>, with newElements: C
  ) where C.Iterator.Element == Iterator.Element, R.Bound == Index

  public mutating func removeSubrange<R: RangeExpression>(
    _ subrange: ${Range}<Index>
  ) where R.Bound == Index
}
Additionally, these new ranges will implement appropriate protocols such as CustomStringConvertible.

It is important to note that these new methods and range types are extensions only. They are not protocol requirements, as they should not need to be customized for specific collections. They exist only as shorthand to expand out to the full slicing operation.

The prefix and suffix methods that take an index are currently protocol requirements, but should not be. This proposal will fix that as a side-effect.

Where PartialRangeFrom is a Sequence, it is left up to the type of Index to control the behavior when the type is incremented past its bounds. In the case of an Int, the iterator will trap when iterating past Int.max. Other types, such as a BigInt that could be incremented indefinitely, would behave differently.

Source compatibility

The new operators/types are purely additive so have no source compatibility consequences. Replacing the overloads taking concrete ranges other than Range with a single generic version is source compatible. prefix and suffix will be deprecated in Swift 4 and later removed.

Effect on ABI stability

The prefix/suffix methods being deprecated should be eliminated before declaring ABI stability.

Effect on API resilience

The new operators/types are purely additive so have no resilience consequences.

Alternatives considered

i... is favored over i..< because the latter is ugly. We have to pick one, two would be redundant and likely to cause confusion over which is the “right” one. Either would be reasonable on pedantic correctness grounds – (i as Int)... includes Int.max consistent with ..., whereas a[i...] is interpreted as a[i..<a.endIndex] consistent with i..<.

It might be nice to consider extend this domain-specific language inside the subscript in other ways. For example, to be able to incorporate the index distance versions of prefix, or add distance offsets to the indices used within the subscript. This proposal explicitly avoids proposals in this area. Such ideas would be considerably more complex to implement, and would make a good project for investigation by an interested community member, but would not fit within the timeline for Swift 4.


#2

Strong +1, glad to see this happening!

Nevin


(David Hart) #3

I remember being against this feature when it was first discussed long ago. But I’ve since appreciated how elegant it is. I also like the i… was chosen instead of i..<

I guess Range would be a better name for the generic protocol to represent all ranges. But its too late for that now. Correct?

···

On 12 Apr 2017, at 18:40, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:

Hi Swift community,

Another proposal pitch. These operators were mentioned briefly in the String manifesto as prefixing/suffixing is very common with strings.

Online copy here: https://github.com/airspeedswift/swift-evolution/blob/71b819d30676c44234bac1aa999961fc5c39bcf3/proposals/NNNN-OneSidedRanges.md
One-sided Ranges

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Ben Cohen <https://github.com/airspeedswift>, Dave Abrahams <https://github.com/dabrahams>, Brent Royal-Gordon <https://github.com/brentdax>
Review Manager: TBD
Status: Awaiting review
Introduction

This proposal introduces the concept of a “one-sided” range, created via prefix/postfix versions of the existing range operators.

It also introduces a new protocol, RangeExpression, to simplify the creation of methods that take different kinds of ranges.

Motivation

It is common, given an index into a collection, to want a slice up to or from that index versus the start/end.

For example (assuming String is once more a Collection):

let s = "Hello, World!"
let i = s.index(where: ",")
let greeting = s[s.startIndex..<i]
When performing lots of slicing like this, the verbosity of repeating s.startIndex is tiresome to write and harmful to readability.

Swift 3’s solution to this is a family of methods:

let greeting = s.prefix(upTo: i)
let withComma = s.prefix(through: i)
let location = s.suffix(from: i)
The two very different-looking ways to perform a similar task is jarring. And as methods, the result cannot be used as an l-value.

A variant of the one-sided slicing syntax found in Python (i.e. s[i:]) is proposed to resolve this.

Proposed solution

Introduce a one-sided range syntax, where the “missing” side is inferred to be the start/end:

// half-open right-handed range
let greeting = s[..<i]
// closed right-handed range
let withComma = s[...i]
// left-handed range (no need for half-open variant)
let location = s[i...]
Additionally, when the index is a countable type, i... should form a Sequence that counts up from i indefinitely. This is useful in forming variants of Sequence.enumerated() when you either want them non-zero-based i.e. zip(1..., greeting), or want to flip the order i.e. zip(greeting, 0...).

This syntax would supercede the existing prefix and suffix operations that take indices, which will be deprecated in a later release. Note that the versions that take distances are not covered by this proposal, and would remain.

This will require the introduction of new range types (e.g. PartialRangeThrough). There are already multiple range types (e.g. ClosedRange, CountableHalfOpenRange), which require overloads to allow them to be used whereever a Range can be.

To unify these different range types, a new protocol, RangeExpression will be created and all ranges conformed to it. Existing overloads taking concrete types other than Range can then be replaced with a single generic method that takes a RangeExpression, converts it to a Range, and then forward the method on.

A generic version of ~= will also be implemented for all range expressions:

switch i {
case 9001...: print("It’s over NINE THOUSAAAAAAAND")
default: print("There's no way that can be right!")
}
The existing concrete overloads that take ranges other than Range will be deprecated in favor of generic ones that take a RangeExpression.

Detailed design

Add the following to the standard library:

(a fuller work-in-progress implementation can be found here: https://github.com/apple/swift/pull/8710)

NOTE: The following is subject to change depending on pending compiler features. Methods may actually be on underscored protocols, and then moved once recursive protocols are implemented. Types may be collapsed using conditional conformance. This should not matter from a usage perspective – users are not expected to use these types directly or override any of the behaviors in their own types. Any final implementation will follow the below in spirit if not in practice.

public protocol RangeExpression {
    associatedtype Bound: Comparable

    /// Returns `self` expressed as a range of indices within `collection`.
    ///
    /// -Parameter collection: The collection `self` should be
    /// relative to.
    ///
    /// -Returns: A `Range<Bound>` suitable for slicing `collection`.
    /// The return value is *not* guaranteed to be inside
    /// its bounds. Callers should apply the same preconditions
    /// to the return value as they would to a range provided
    /// directly by the user.
    func relative<C: _Indexable>(to collection: C) -> Range<Bound> where C.Index == Bound

    func contains(_ element: Bound) -> Bool
}

extension RangeExpression {
  public static func ~= (pattern: Self, value: Bound) -> Bool
}

prefix operator ..<
public struct PartialRangeUpTo<T: Comparable>: RangeExpression {
  public init(_ upperBound: T) { self.upperBound = upperBound }
  public let upperBound: T
}
extension Comparable {
  public static prefix func ..<(x: Self) -> PartialRangeUpTo<Self>
}

prefix operator ...
public struct PartialRangeThrough<T: Comparable>: RangeExpression {
  public init(_ upperBound: T)
  public let upperBound: T
}
extension Comparable {
  public static prefix func ...(x: Self) -> PartialRangeThrough<Self>
}

postfix operator ...
public struct PartialRangeFrom<T: Comparable>: RangeExpression {
  public init(_ lowerBound: T)
  public let lowerBound: T
}
extension Comparable {
  public static postfix func ...(x: Self) -> PartialRangeFrom<Self>
}

// The below relies on Conditional Conformance. Pending that feature,
// this may require an additional CountablePartialRangeFrom type temporarily.
extension PartialRangeFrom: Sequence
  where Index: _Strideable, Index.Stride : SignedInteger

extension Collection {
  public subscript<R: RangeExpression>(r: R) -> SubSequence
   where R.Bound == Index { get }
}
extension MutableCollection {
  public subscript<R: RangeExpression>(r: R) -> SubSequence
   where R.Bound == Index { get set }
}
  
extension RangeReplaceableColleciton {
  public mutating func replaceSubrange<C: Collection, R: RangeExpression>(
    _ subrange: ${Range}<Index>, with newElements: C
  ) where C.Iterator.Element == Iterator.Element, R.Bound == Index

  public mutating func removeSubrange<R: RangeExpression>(
    _ subrange: ${Range}<Index>
  ) where R.Bound == Index
}
Additionally, these new ranges will implement appropriate protocols such as CustomStringConvertible.

It is important to note that these new methods and range types are extensions only. They are not protocol requirements, as they should not need to be customized for specific collections. They exist only as shorthand to expand out to the full slicing operation.

The prefix and suffix methods that take an index are currently protocol requirements, but should not be. This proposal will fix that as a side-effect.

Where PartialRangeFrom is a Sequence, it is left up to the type of Index to control the behavior when the type is incremented past its bounds. In the case of an Int, the iterator will trap when iterating past Int.max. Other types, such as a BigInt that could be incremented indefinitely, would behave differently.

Source compatibility

The new operators/types are purely additive so have no source compatibility consequences. Replacing the overloads taking concrete ranges other than Range with a single generic version is source compatible. prefix and suffix will be deprecated in Swift 4 and later removed.

Effect on ABI stability

The prefix/suffix methods being deprecated should be eliminated before declaring ABI stability.

Effect on API resilience

The new operators/types are purely additive so have no resilience consequences.

Alternatives considered

i... is favored over i..< because the latter is ugly. We have to pick one, two would be redundant and likely to cause confusion over which is the “right” one. Either would be reasonable on pedantic correctness grounds – (i as Int)... includes Int.max consistent with ..., whereas a[i...] is interpreted as a[i..<a.endIndex] consistent with i..<.

It might be nice to consider extend this domain-specific language inside the subscript in other ways. For example, to be able to incorporate the index distance versions of prefix, or add distance offsets to the indices used within the subscript. This proposal explicitly avoids proposals in this area. Such ideas would be considerably more complex to implement, and would make a good project for investigation by an interested community member, but would not fit within the timeline for Swift 4.

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


(Haravikk) #4

I like the principle in general, but I have some concerns about the range syntax. Firstly my concern is that allowing either end of the range to be omitted feels like a possible bug to me, so I'm not sure if we should encourage that?

I'm wondering if a slightly better alternative might to be to retain the operators as binary but to pass Void, like so:

  let rangeFrom = 5...()
  let rangeTo = ()...5

And so-on. It's not quite as pretty, but makes it clear that no mistake was made, and allows the operators to be defined normally taking two arguments of Comparable and Void (and vice versa).

It could be neatened up if we could allow a lone underscore as Void, like so:

  let rangeFrom = 5..._
  let rangeTo = _...5

This is a bit neater looking, and should be consistent with how underscore is used elsewhere? I'm not sure if it might conflict though, but I don't think so.

Just I thought, but I dislike the idea that by forgetting a value on a range, or making some other typo, I could accidentally define an open ended range and change the behaviour of something that accepts both open and closed ranges, I think requiring something that explicitly indicates an open range is a bit better.

···

On 12 Apr 2017, at 17:40, Ben Cohen via swift-evolution <swift-evolution@swift.org> wrote:

Hi Swift community,

Another proposal pitch. These operators were mentioned briefly in the String manifesto as prefixing/suffixing is very common with strings.

Online copy here: https://github.com/airspeedswift/swift-evolution/blob/71b819d30676c44234bac1aa999961fc5c39bcf3/proposals/NNNN-OneSidedRanges.md
One-sided Ranges

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Ben Cohen <https://github.com/airspeedswift>, Dave Abrahams <https://github.com/dabrahams>, Brent Royal-Gordon <https://github.com/brentdax>
Review Manager: TBD
Status: Awaiting review
Introduction

This proposal introduces the concept of a “one-sided” range, created via prefix/postfix versions of the existing range operators.

It also introduces a new protocol, RangeExpression, to simplify the creation of methods that take different kinds of ranges.

Motivation

It is common, given an index into a collection, to want a slice up to or from that index versus the start/end.

For example (assuming String is once more a Collection):

let s = "Hello, World!"
let i = s.index(where: ",")
let greeting = s[s.startIndex..<i]
When performing lots of slicing like this, the verbosity of repeating s.startIndex is tiresome to write and harmful to readability.

Swift 3’s solution to this is a family of methods:

let greeting = s.prefix(upTo: i)
let withComma = s.prefix(through: i)
let location = s.suffix(from: i)
The two very different-looking ways to perform a similar task is jarring. And as methods, the result cannot be used as an l-value.

A variant of the one-sided slicing syntax found in Python (i.e. s[i:]) is proposed to resolve this.

Proposed solution

Introduce a one-sided range syntax, where the “missing” side is inferred to be the start/end:

// half-open right-handed range
let greeting = s[..<i]
// closed right-handed range
let withComma = s[...i]
// left-handed range (no need for half-open variant)
let location = s[i...]
Additionally, when the index is a countable type, i... should form a Sequence that counts up from i indefinitely. This is useful in forming variants of Sequence.enumerated() when you either want them non-zero-based i.e. zip(1..., greeting), or want to flip the order i.e. zip(greeting, 0...).

This syntax would supercede the existing prefix and suffix operations that take indices, which will be deprecated in a later release. Note that the versions that take distances are not covered by this proposal, and would remain.

This will require the introduction of new range types (e.g. PartialRangeThrough). There are already multiple range types (e.g. ClosedRange, CountableHalfOpenRange), which require overloads to allow them to be used whereever a Range can be.

To unify these different range types, a new protocol, RangeExpression will be created and all ranges conformed to it. Existing overloads taking concrete types other than Range can then be replaced with a single generic method that takes a RangeExpression, converts it to a Range, and then forward the method on.

A generic version of ~= will also be implemented for all range expressions:

switch i {
case 9001...: print("It’s over NINE THOUSAAAAAAAND")
default: print("There's no way that can be right!")
}
The existing concrete overloads that take ranges other than Range will be deprecated in favor of generic ones that take a RangeExpression.

Detailed design

Add the following to the standard library:

(a fuller work-in-progress implementation can be found here: https://github.com/apple/swift/pull/8710)

NOTE: The following is subject to change depending on pending compiler features. Methods may actually be on underscored protocols, and then moved once recursive protocols are implemented. Types may be collapsed using conditional conformance. This should not matter from a usage perspective – users are not expected to use these types directly or override any of the behaviors in their own types. Any final implementation will follow the below in spirit if not in practice.

public protocol RangeExpression {
    associatedtype Bound: Comparable

    /// Returns `self` expressed as a range of indices within `collection`.
    ///
    /// -Parameter collection: The collection `self` should be
    /// relative to.
    ///
    /// -Returns: A `Range<Bound>` suitable for slicing `collection`.
    /// The return value is *not* guaranteed to be inside
    /// its bounds. Callers should apply the same preconditions
    /// to the return value as they would to a range provided
    /// directly by the user.
    func relative<C: _Indexable>(to collection: C) -> Range<Bound> where C.Index == Bound

    func contains(_ element: Bound) -> Bool
}

extension RangeExpression {
  public static func ~= (pattern: Self, value: Bound) -> Bool
}

prefix operator ..<
public struct PartialRangeUpTo<T: Comparable>: RangeExpression {
  public init(_ upperBound: T) { self.upperBound = upperBound }
  public let upperBound: T
}
extension Comparable {
  public static prefix func ..<(x: Self) -> PartialRangeUpTo<Self>
}

prefix operator ...
public struct PartialRangeThrough<T: Comparable>: RangeExpression {
  public init(_ upperBound: T)
  public let upperBound: T
}
extension Comparable {
  public static prefix func ...(x: Self) -> PartialRangeThrough<Self>
}

postfix operator ...
public struct PartialRangeFrom<T: Comparable>: RangeExpression {
  public init(_ lowerBound: T)
  public let lowerBound: T
}
extension Comparable {
  public static postfix func ...(x: Self) -> PartialRangeFrom<Self>
}

// The below relies on Conditional Conformance. Pending that feature,
// this may require an additional CountablePartialRangeFrom type temporarily.
extension PartialRangeFrom: Sequence
  where Index: _Strideable, Index.Stride : SignedInteger

extension Collection {
  public subscript<R: RangeExpression>(r: R) -> SubSequence
   where R.Bound == Index { get }
}
extension MutableCollection {
  public subscript<R: RangeExpression>(r: R) -> SubSequence
   where R.Bound == Index { get set }
}
  
extension RangeReplaceableColleciton {
  public mutating func replaceSubrange<C: Collection, R: RangeExpression>(
    _ subrange: ${Range}<Index>, with newElements: C
  ) where C.Iterator.Element == Iterator.Element, R.Bound == Index

  public mutating func removeSubrange<R: RangeExpression>(
    _ subrange: ${Range}<Index>
  ) where R.Bound == Index
}
Additionally, these new ranges will implement appropriate protocols such as CustomStringConvertible.

It is important to note that these new methods and range types are extensions only. They are not protocol requirements, as they should not need to be customized for specific collections. They exist only as shorthand to expand out to the full slicing operation.

The prefix and suffix methods that take an index are currently protocol requirements, but should not be. This proposal will fix that as a side-effect.

Where PartialRangeFrom is a Sequence, it is left up to the type of Index to control the behavior when the type is incremented past its bounds. In the case of an Int, the iterator will trap when iterating past Int.max. Other types, such as a BigInt that could be incremented indefinitely, would behave differently.

Source compatibility

The new operators/types are purely additive so have no source compatibility consequences. Replacing the overloads taking concrete ranges other than Range with a single generic version is source compatible. prefix and suffix will be deprecated in Swift 4 and later removed.

Effect on ABI stability

The prefix/suffix methods being deprecated should be eliminated before declaring ABI stability.

Effect on API resilience

The new operators/types are purely additive so have no resilience consequences.

Alternatives considered

i... is favored over i..< because the latter is ugly. We have to pick one, two would be redundant and likely to cause confusion over which is the “right” one. Either would be reasonable on pedantic correctness grounds – (i as Int)... includes Int.max consistent with ..., whereas a[i...] is interpreted as a[i..<a.endIndex] consistent with i..<.

It might be nice to consider extend this domain-specific language inside the subscript in other ways. For example, to be able to incorporate the index distance versions of prefix, or add distance offsets to the indices used within the subscript. This proposal explicitly avoids proposals in this area. Such ideas would be considerably more complex to implement, and would make a good project for investigation by an interested community member, but would not fit within the timeline for Swift 4.

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


(Félix Cloutier) #5

I don't have a strong opinion; are we sure enough that this is what we want the postfix operator … to be for? For instance, C++ uses it a lot with variadic templates.

···

Le 12 avr. 2017 à 13:21, David Hart via swift-evolution <swift-evolution@swift.org> a écrit :

I remember being against this feature when it was first discussed long ago. But I’ve since appreciated how elegant it is. I also like the i… was chosen instead of i..<

I guess Range would be a better name for the generic protocol to represent all ranges. But its too late for that now. Correct?

On 12 Apr 2017, at 18:40, Ben Cohen via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Hi Swift community,

Another proposal pitch. These operators were mentioned briefly in the String manifesto as prefixing/suffixing is very common with strings.

Online copy here: https://github.com/airspeedswift/swift-evolution/blob/71b819d30676c44234bac1aa999961fc5c39bcf3/proposals/NNNN-OneSidedRanges.md
One-sided Ranges

Proposal: SE-NNNN <file:///Users/ben_cohen/Documents/swift-evolution/proposals/NNNN-filename.md>
Authors: Ben Cohen <https://github.com/airspeedswift>, Dave Abrahams <https://github.com/dabrahams>, Brent Royal-Gordon <https://github.com/brentdax>
Review Manager: TBD
Status: Awaiting review
Introduction

This proposal introduces the concept of a “one-sided” range, created via prefix/postfix versions of the existing range operators.

It also introduces a new protocol, RangeExpression, to simplify the creation of methods that take different kinds of ranges.

Motivation

It is common, given an index into a collection, to want a slice up to or from that index versus the start/end.

For example (assuming String is once more a Collection):

let s = "Hello, World!"
let i = s.index(where: ",")
let greeting = s[s.startIndex..<i]
When performing lots of slicing like this, the verbosity of repeating s.startIndex is tiresome to write and harmful to readability.

Swift 3’s solution to this is a family of methods:

let greeting = s.prefix(upTo: i)
let withComma = s.prefix(through: i)
let location = s.suffix(from: i)
The two very different-looking ways to perform a similar task is jarring. And as methods, the result cannot be used as an l-value.

A variant of the one-sided slicing syntax found in Python (i.e. s[i:]) is proposed to resolve this.

Proposed solution

Introduce a one-sided range syntax, where the “missing” side is inferred to be the start/end:

// half-open right-handed range
let greeting = s[..<i]
// closed right-handed range
let withComma = s[...i]
// left-handed range (no need for half-open variant)
let location = s[i...]
Additionally, when the index is a countable type, i... should form a Sequence that counts up from i indefinitely. This is useful in forming variants of Sequence.enumerated() when you either want them non-zero-based i.e. zip(1..., greeting), or want to flip the order i.e. zip(greeting, 0...).

This syntax would supercede the existing prefix and suffix operations that take indices, which will be deprecated in a later release. Note that the versions that take distances are not covered by this proposal, and would remain.

This will require the introduction of new range types (e.g. PartialRangeThrough). There are already multiple range types (e.g. ClosedRange, CountableHalfOpenRange), which require overloads to allow them to be used whereever a Range can be.

To unify these different range types, a new protocol, RangeExpression will be created and all ranges conformed to it. Existing overloads taking concrete types other than Range can then be replaced with a single generic method that takes a RangeExpression, converts it to a Range, and then forward the method on.

A generic version of ~= will also be implemented for all range expressions:

switch i {
case 9001...: print("It’s over NINE THOUSAAAAAAAND")
default: print("There's no way that can be right!")
}
The existing concrete overloads that take ranges other than Range will be deprecated in favor of generic ones that take a RangeExpression.

Detailed design

Add the following to the standard library:

(a fuller work-in-progress implementation can be found here: https://github.com/apple/swift/pull/8710)

NOTE: The following is subject to change depending on pending compiler features. Methods may actually be on underscored protocols, and then moved once recursive protocols are implemented. Types may be collapsed using conditional conformance. This should not matter from a usage perspective – users are not expected to use these types directly or override any of the behaviors in their own types. Any final implementation will follow the below in spirit if not in practice.

public protocol RangeExpression {
    associatedtype Bound: Comparable

    /// Returns `self` expressed as a range of indices within `collection`.
    ///
    /// -Parameter collection: The collection `self` should be
    /// relative to.
    ///
    /// -Returns: A `Range<Bound>` suitable for slicing `collection`.
    /// The return value is *not* guaranteed to be inside
    /// its bounds. Callers should apply the same preconditions
    /// to the return value as they would to a range provided
    /// directly by the user.
    func relative<C: _Indexable>(to collection: C) -> Range<Bound> where C.Index == Bound

    func contains(_ element: Bound) -> Bool
}

extension RangeExpression {
  public static func ~= (pattern: Self, value: Bound) -> Bool
}

prefix operator ..<
public struct PartialRangeUpTo<T: Comparable>: RangeExpression {
  public init(_ upperBound: T) { self.upperBound = upperBound }
  public let upperBound: T
}
extension Comparable {
  public static prefix func ..<(x: Self) -> PartialRangeUpTo<Self>
}

prefix operator ...
public struct PartialRangeThrough<T: Comparable>: RangeExpression {
  public init(_ upperBound: T)
  public let upperBound: T
}
extension Comparable {
  public static prefix func ...(x: Self) -> PartialRangeThrough<Self>
}

postfix operator ...
public struct PartialRangeFrom<T: Comparable>: RangeExpression {
  public init(_ lowerBound: T)
  public let lowerBound: T
}
extension Comparable {
  public static postfix func ...(x: Self) -> PartialRangeFrom<Self>
}

// The below relies on Conditional Conformance. Pending that feature,
// this may require an additional CountablePartialRangeFrom type temporarily.
extension PartialRangeFrom: Sequence
  where Index: _Strideable, Index.Stride : SignedInteger

extension Collection {
  public subscript<R: RangeExpression>(r: R) -> SubSequence
   where R.Bound == Index { get }
}
extension MutableCollection {
  public subscript<R: RangeExpression>(r: R) -> SubSequence
   where R.Bound == Index { get set }
}
  
extension RangeReplaceableColleciton {
  public mutating func replaceSubrange<C: Collection, R: RangeExpression>(
    _ subrange: ${Range}<Index>, with newElements: C
  ) where C.Iterator.Element == Iterator.Element, R.Bound == Index

  public mutating func removeSubrange<R: RangeExpression>(
    _ subrange: ${Range}<Index>
  ) where R.Bound == Index
}
Additionally, these new ranges will implement appropriate protocols such as CustomStringConvertible.

It is important to note that these new methods and range types are extensions only. They are not protocol requirements, as they should not need to be customized for specific collections. They exist only as shorthand to expand out to the full slicing operation.

The prefix and suffix methods that take an index are currently protocol requirements, but should not be. This proposal will fix that as a side-effect.

Where PartialRangeFrom is a Sequence, it is left up to the type of Index to control the behavior when the type is incremented past its bounds. In the case of an Int, the iterator will trap when iterating past Int.max. Other types, such as a BigInt that could be incremented indefinitely, would behave differently.

Source compatibility

The new operators/types are purely additive so have no source compatibility consequences. Replacing the overloads taking concrete ranges other than Range with a single generic version is source compatible. prefix and suffix will be deprecated in Swift 4 and later removed.

Effect on ABI stability

The prefix/suffix methods being deprecated should be eliminated before declaring ABI stability.

Effect on API resilience

The new operators/types are purely additive so have no resilience consequences.

Alternatives considered

i... is favored over i..< because the latter is ugly. We have to pick one, two would be redundant and likely to cause confusion over which is the “right” one. Either would be reasonable on pedantic correctness grounds – (i as Int)... includes Int.max consistent with ..., whereas a[i...] is interpreted as a[i..<a.endIndex] consistent with i..<.

It might be nice to consider extend this domain-specific language inside the subscript in other ways. For example, to be able to incorporate the index distance versions of prefix, or add distance offsets to the indices used within the subscript. This proposal explicitly avoids proposals in this area. Such ideas would be considerably more complex to implement, and would make a good project for investigation by an interested community member, but would not fit within the timeline for Swift 4.

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

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


(David Sweeris) #6

I don't think the two usages conflict... maybe later if "literal values as generic parameters" and "variadic generic parameters" get added, there might be a problem involving variadic literal one-sided ranges, but otherwise we should be good on that front... I think...

I should probably learn more about how C++ templates have changed since they were first introduced.

- Dave Sweeris

···

On Apr 12, 2017, at 20:31, Félix Cloutier via swift-evolution <swift-evolution@swift.org> wrote:

I don't have a strong opinion; are we sure enough that this is what we want the postfix operator … to be for? For instance, C++ uses it a lot with variadic templates.


(Félix Cloutier) #7

template<typename... T>
void foo(T... args)
{
  return bar(args...);
}

In this bad but simple example, bar is called with the same* parameters as foo. Parameter unpacking uses the postfix … operator.

* To some extent. Doing the right thing adds a lot of noise.

···

Le 13 avr. 2017 à 11:18, David Sweeris <davesweeris@mac.com> a écrit :

On Apr 12, 2017, at 20:31, Félix Cloutier via swift-evolution <swift-evolution@swift.org> wrote:

I don't have a strong opinion; are we sure enough that this is what we want the postfix operator … to be for? For instance, C++ uses it a lot with variadic templates.

I don't think the two usages conflict... maybe later if "literal values as generic parameters" and "variadic generic parameters" get added, there might be a problem involving variadic literal one-sided ranges, but otherwise we should be good on that front... I think...

I should probably learn more about how C++ templates have changed since they were first introduced.

- Dave Sweeris


(Brent Royal-Gordon) #8

I want to see tuple splat and variadic generics one day, but I think partial ranges will be used more often. We can give parameter unpacking a heavier syntax.

···

On Apr 13, 2017, at 7:29 PM, Félix Cloutier via swift-evolution <swift-evolution@swift.org> wrote:

template<typename... T>
void foo(T... args)
{
  return bar(args...);
}

In this bad but simple example, bar is called with the same* parameters as foo. Parameter unpacking uses the postfix … operator.

* To some extent. Doing the right thing adds a lot of noise.

--
Brent Royal-Gordon
Architechies


(Haravikk) #9

Apologies if this comes through as a duplicate for some people, but I'm not sure if it went through the first time; I seem to have some trouble with ProofPoint, who apparently do not monitor their false positive reporting system. As such my mail server is still listed from eight months ago despite never having a single spam message reported in that time, so pretty sure ProofPoint is a massive waste of money to anyone having it inflicted upon them, as it seemingly blocks entire servers with no negative rating.

Anyway, I'll repost for anyone that didn't get it the first time; if you ignored it the first time then feel free to do-so again, just know that it shall do irreparable harm to my fragile ego:

I like the principle in general, but I have some concerns about the range syntax. Firstly my concern is that allowing either end of the range to be omitted feels like a possible bug to me, so I'm not sure if we should encourage that?

I'm wondering if a slightly better alternative might to be to retain the operators as binary but to pass Void, like so:

  let rangeFrom = 5...()
  let rangeTo = ()...5

And so-on. It's not quite as pretty, but makes it clear that no mistake was made, and allows the operators to be defined normally taking two arguments of Comparable and Void (and vice versa).

It could be neatened up if we could allow a lone underscore as Void, like so:

  let rangeFrom = 5..._
  let rangeTo = _...5

This is a bit neater looking, and should be consistent with how underscore is used elsewhere? I'm not sure if it might conflict though, but I don't think so.

Just I thought, but I dislike the idea that by forgetting a value on a range, or making some other typo, I could accidentally define an open ended range and change the behaviour of something that accepts both open and closed ranges, I think requiring something that explicitly indicates an open range is a bit better.