Shorthand for Offsetting startIndex and endIndex

[palimondo (Pavol Vaskovic)]

@Letan

...what are we solving? If it is the unification of the slice family I don’t think that this is the way to go.
…
I think we need a simpler solution and python’s slicing seems like a good concession to make.

+💯

Given this topic isn’t here the first time, maybe it helps to identify hotspots of contention and confusion:

• Collection’s slicing overloads for Sequence methods (prefix, suffix, dropFirst, dropLast) — general unification of these to adopt subscript as shorthand syntax
• Concerns over performance characteristics of subscript arithmetic for non-Integer backed indices in light of performance guarantees vis-à-vis Collection protocol family
• Mutating subscripted slice @dabrahams brought up

I have re-read this thread again, and it is not clear to me what would be reasons against adopting something like @Letan's .. solution as relative arithmetic against start index and end indexes. I would maybe change the name to SliceRange and propose we borrow Python's terminology for these operations on Sequence and Collection, calling it slicing.

I believe this is closes to what @Ben_Cohen and @dabrahams were describing as future directions in Strings in Swift 4 :

@Ben_Cohen

Prefix and suffix operations should be migrated to be subscripting operations with one-sided ranges i.e. s.prefix(upTo: i) should become s[..<i]

Slicing a Sequence

SliceRange describes Sequence operations that return subsequence relative to the specified bounds. It is formed using the .. operator from integer bounds. Positive bounds are relative to the start of the sequence. Negative bounds are relative to the end of the sequence.

Half-Bounded SliceRange

Sequence Slice	Condition	Equivalent Sequence Operations
s[i..]	0 <= i	s.dropFirst(i)
	i < 0	s.suffix(abs(i))
s[..i]	0 <= i	s.prefix(i)
	i < 0	s.dropLast(abs(i))
Edit: fixed, thanks to @QuinceyMorris

Bounded SliceRange : s[i..j]

Conditions	0 <= j	j < 0
0 <= i	s.prefix(j).dropFirst(i)	s.dropFirst(i).dropLast(abs(j))
i < 0	unsupported	s.suffix(abs(i)).dropLast(abs(j))

The SliceRange combination with lowerBound from end of the sequence and upperBound from start of sequence is not supported for Sequence, because it can not be expressed in terms of successive sequence operations without knowing the sequence length. This limitation could be potentially lifted, if I wasn’t aiming to express the slices in terms of sequence ops. The suffix implementation is accumulating data in buffer, keeping an element count from the beginning to trim the resulting sequence is doable.

Here’s fully working implementation sketch I’ve put together in a Playground:

infix operator .. : RangeFormationPrecedence
prefix operator ..
postfix operator ..
prefix operator ..-
infix operator ..- : RangeFormationPrecedence

public struct SliceRange {
    var lowerBound: Int
    var upperBound: Int?
}

func ..(lhs: Int, rhs: Int) -> SliceRange {
    return SliceRange(lowerBound: lhs, upperBound: rhs)
}

prefix func ..(upperBound: Int) -> SliceRange {
    return SliceRange(lowerBound: 0, upperBound: upperBound)
}

postfix func ..(lowerBound: Int) -> SliceRange {
    return SliceRange(lowerBound: lowerBound, upperBound: nil)
}

// Negating `SliceRange` to allow slices with lower bound
// relative to the end of `Sequence`
public prefix func -(slice: SliceRange) -> SliceRange {
    return SliceRange(lowerBound: -slice.lowerBound,
                      upperBound: slice.upperBound)
}

// Resolves unary operator juxtaposition of `..` and `-` for
// `SliceRange` with upper bound from the end of `Sequence`
public prefix func ..-(upperBound: Int) -> SliceRange {
    return ..(-upperBound)
}

public func ..-(lowerBound: Int, upperBound: Int) -> SliceRange {
    return lowerBound..(-upperBound)
}


extension Sequence {
    subscript(slice: SliceRange) -> SubSequence {
        switch (slice.lowerBound, slice.upperBound) {
        case (0, .some(let upTo)) where 0 <= upTo:
            return self.prefix(upTo)
        case (0, .some(let n)) where n < 0:
            return self.dropLast(-n)
        case (let n, nil) where 0 <= n:
            return self.dropFirst(n)
        case (let length, nil) where length < 0:
            return self.suffix(-length)
        case (let n, .some(let upTo)) where 0 <= n && 0 <= upTo:
//            return self.prefix(upTo).dropFirst(n)
// Value of type 'Self.SubSequence' has no member 'dropFirst'
            return (self.prefix(upTo) as! AnySequence<Element>)
                .dropFirst(n) as! Self.SubSequence
        case (let n, .some(let upTo)) where 0 <= n && upTo < 0:
//            return self.dropFirst(n).dropLast(-upTo)
            return (self.dropFirst(n) as! AnySequence<Element>)
                .dropLast(-upTo) as! Self.SubSequence
        case (let length, .some(let upTo)) where length < 0 && 0 <= upTo:
            fatalError("Unsuported SliceRange combination for Sequence: lowerBound from end of the sequence and upperBound from start of sequence.")
        case (let n, .some(let upTo)) where n < 0 && upTo < 0:
// XXX Why is the forced cast suggested by compiler necessary???
            return self.suffix(-n).dropLast(-upTo) as! Self.SubSequence
        default:
            fatalError("Unexpected combination: " + String(describing: slice))
        }
    }
}


// Tests

let seq = sequence(first: 0) { $0 < 6 - 1 ? $0 &+ 1 : nil }

print(Array(  seq             )) // [0, 1, 2, 3, 4, 5]
print(Array(  seq[2..]        )) // [2, 3, 4, 5]
print(Array(  seq[..2]        )) // [0, 1]
print(Array(  seq[(-2)..]     )) // [4, 5]
print(Array(  seq[-2..]       )) // [4, 5]
print(Array(  seq[..(-2)]     )) // [0, 1, 2, 3]
print(Array(  seq[..-2]       )) // [0, 1, 2, 3]
print(Array(  seq[2..4]       )) // [2, 3]
print(Array(  seq[2..(-1)]    )) // [2, 3, 4]
print(Array(  seq[2..-1]      )) // [2, 3, 4]
//print(Array(  seq[-5..3]      )) // unsupported combination
print(Array(  seq[-3..(-1)]   )) // [3, 4]
print(Array(  seq[-3..-1]     )) // [3, 4]

Slicing a Collection

I don’t have an up-to-date master build on hand, but I don’t seen any fundamental obstacles to using @Letan’s code:

extension SliceRange: RangeExpression {
    public func relative<C: Collection>(to collection: C) -> Range<Bound>
        where C.Index == Bound {
            let startBase = lowerBound < 0
                ? collection.endIndex
                : collection.startIndex
            let endBase = upperBound == nil || upperBound! < 0
                ? collection.endIndex
                : collection.startIndex
            
            let start = collection.index(startBase, offsetBy: lowerBound)
            let end = collection.index(endBase, offsetBy: upperBound ?? 0)
            
            return start..<end
    }
}

To address the performance concerns, we should clearly document that SliceRange conversion to Range (via RangeExpression protocol conformance) performs computation whose performance guarantees are given by the underlying collection.

I’m not sure if the above slicing implementation for Collections automatically works for mutable range modifications as @dabrahams mentions above… Does it?