Range.contains(Range) currently checks all values instead of a bounds check, taking a very long time for large ranges.

[carlynorama]

Description

The ClosedRange.contains(ClosedRange) check on seems to currently inherit from Collection which expands out all the values and checks each one. This means large ranges take a very long time to complete a .contains() check.

Reproduction

public extension ClosedRange<Int> {
    func containsCheck(by other: ClosedRange<Int>) -> [ClosedRange<Int>] {
        //print("cropping...")
        
        
         //HANGS when the ranges are large.
         guard !other.contains(self) else {
             print("other contains source entirely. Nothing left over.")
             return []
         }
        
        //Bounds check to the rescue.
        
        guard !other.fullyContains(self) else {
            print("other contains source entirely. Nothing left over.")
            return []
        }
        
        //Already fast.
        if self.contains(other.lowerBound) {
            //print("found lower")
            return [self.lowerBound...other.lowerBound-1]
        } else if self.contains(other.upperBound) {
            //print("found upper")
            return [other.upperBound+1...self.upperBound]
        } else {
            fatalError("Range divide:Forgot something...")
        }
        
    }
    func fullyContains(_ other: ClosedRange<Int>) -> Bool {
        self.lowerBound < other.lowerBound && self.upperBound > other.upperBound
    }
}

let resultC = (2442...2679).containsCheck(by:2321...2446)
print(resultC)

print(Int.max)

let resultD = (2442763622...2679835230).containsCheck(by:2321931404...2446354471)
//let result = (0...9).crop(by:3...8)
print(resultD)

Expected behavior

Range.contains(element) appears to already be optimized as a bounds check. I expected Range.contains(Range) would have been the same.

Environment

swift-driver version: 1.87.1 Apple Swift version 5.9 (swiftlang-5.9.0.128.108 clang-1500.0.40.1)
Target: arm64-apple-macosx14.0

Additional information

Forum discussion, discovered as part of Advent of Code 2023

[carlynorama]

(note, that the fullyContains function was written in the context where overlap had already been checked for.

self.contains(other.lowerBound) && self.contains(other.upperBound)

would be better for a stand alone. )

[akbashev]

Possibly related
swiftlang/swift-experimental-string-processing#694