mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
366 lines
12 KiB
Swift
366 lines
12 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2023 - 2026 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#if compiler(>=6.2) && !$Embedded
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
public struct BigSubstring: Sendable {
|
|
var _base: BigString
|
|
var _bounds: Range<Index>
|
|
|
|
public init(_unchecked base: BigString, in bounds: Range<Index>) {
|
|
assert(bounds.lowerBound == base.index(roundingDown: bounds.lowerBound))
|
|
assert(bounds.upperBound == base.index(roundingDown: bounds.upperBound))
|
|
self._base = base
|
|
self._bounds = bounds
|
|
}
|
|
|
|
public init(_ base: BigString, in bounds: Range<Index>) {
|
|
self._base = base
|
|
// Sub-character slicing could change character boundaries in the tree, requiring
|
|
// resyncing metadata. This would not be acceptable to do during slicing, so let's
|
|
// round substring bounds down to the nearest character.
|
|
let start = base.index(roundingDown: bounds.lowerBound)
|
|
let end = base.index(roundingDown: bounds.upperBound)
|
|
self._bounds = Range(uncheckedBounds: (start, end))
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring {
|
|
public var base: BigString { _base }
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: CustomStringConvertible {
|
|
public var description: String {
|
|
String(_from: _base, in: _bounds)
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: CustomDebugStringConvertible {
|
|
public var debugDescription: String {
|
|
description.debugDescription
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: ExpressibleByStringLiteral {
|
|
public init(stringLiteral value: String) {
|
|
self.init(value)
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: LosslessStringConvertible {
|
|
// init?(_: String) is implemented by RangeReplaceableCollection.init(_:)
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: Equatable {
|
|
public static func ==(left: Self, right: Self) -> Bool {
|
|
// FIXME: Implement properly normalized comparisons & hashing.
|
|
// This is somewhat tricky as we shouldn't just normalize individual pieces of the string
|
|
// split up on random Character boundaries -- Unicode does not promise that
|
|
// norm(a + c) == norm(a) + norm(b) in this case.
|
|
// To do this properly, we'll probably need to expose new stdlib entry points. :-/
|
|
if left.isIdentical(to: right) { return true }
|
|
|
|
guard left.count == right.count else { return false }
|
|
|
|
// FIXME: Even if we keep doing characterwise comparisons, we should skip over shared subtrees.
|
|
var it1 = left.makeIterator()
|
|
var it2 = right.makeIterator()
|
|
var a: Character? = nil
|
|
var b: Character? = nil
|
|
repeat {
|
|
a = it1.next()
|
|
b = it2.next()
|
|
guard a == b else { return false }
|
|
} while a != nil
|
|
return true
|
|
}
|
|
|
|
public func isIdentical(to other: Self) -> Bool {
|
|
guard self._base.isIdentical(to: other._base) else { return false }
|
|
return self._bounds == other._bounds
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: Hashable {
|
|
public func hash(into hasher: inout Hasher) {
|
|
var it = self.makeIterator()
|
|
while let character = it.next() {
|
|
let s = String(character)
|
|
s._withNFCCodeUnits { hasher.combine($0) }
|
|
}
|
|
hasher.combine(0xFF as UInt8)
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: Comparable {
|
|
public static func < (left: Self, right: Self) -> Bool {
|
|
// FIXME: Implement properly normalized comparisons & hashing.
|
|
// This is somewhat tricky as we shouldn't just normalize individual pieces of the string
|
|
// split up on random Character boundaries -- Unicode does not promise that
|
|
// norm(a + c) == norm(a) + norm(b) in this case.
|
|
// To do this properly, we'll probably need to expose new stdlib entry points. :-/
|
|
if left.isIdentical(to: right) { return false }
|
|
// FIXME: Even if we keep doing characterwise comparisons, we should skip over shared subtrees.
|
|
var it1 = left.makeIterator()
|
|
var it2 = right.makeIterator()
|
|
while true {
|
|
switch (it1.next(), it2.next()) {
|
|
case (nil, nil): return false
|
|
case (nil, .some): return true
|
|
case (.some, nil): return false
|
|
case let (a?, b?):
|
|
if a == b { continue }
|
|
return a < b
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: Sequence {
|
|
public typealias Element = Character
|
|
|
|
public struct Iterator: IteratorProtocol {
|
|
let _end: BigString.Index
|
|
var _it: BigString.Iterator
|
|
|
|
init(_substring: BigSubstring) {
|
|
self._it = BigString.Iterator(_substring._base, from: _substring.startIndex)
|
|
self._end = _substring.endIndex
|
|
}
|
|
|
|
public mutating func next() -> Character? {
|
|
guard _it.isBelow(_end) else { return nil }
|
|
return _it.next()
|
|
}
|
|
}
|
|
|
|
public func makeIterator() -> Iterator {
|
|
Iterator(_substring: self)
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: BidirectionalCollection {
|
|
public typealias Index = BigString.Index
|
|
public typealias SubSequence = Self
|
|
|
|
@inline(__always)
|
|
public var startIndex: Index { _bounds.lowerBound }
|
|
|
|
@inline(__always)
|
|
public var endIndex: Index { _bounds.upperBound }
|
|
|
|
public var count: Int {
|
|
distance(from: _bounds.lowerBound, to: _bounds.upperBound)
|
|
}
|
|
|
|
@inline(__always)
|
|
public func index(after i: Index) -> Index {
|
|
precondition(i < endIndex, "Cannot advance above end index")
|
|
return _base.index(after: i)
|
|
}
|
|
|
|
@inline(__always)
|
|
public func index(before i: Index) -> Index {
|
|
precondition(i > startIndex, "Cannot advance below start index")
|
|
return _base.index(before: i)
|
|
}
|
|
|
|
@inline(__always)
|
|
public func index(_ i: Index, offsetBy distance: Int) -> Index {
|
|
precondition(i >= startIndex && i <= endIndex, "Index out of bounds")
|
|
let j = _base.index(i, offsetBy: distance)
|
|
precondition(j >= startIndex && j <= endIndex, "Index out of bounds")
|
|
return j
|
|
}
|
|
|
|
public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
|
|
precondition(i >= startIndex && i <= endIndex, "Index out of bounds")
|
|
guard let j = _base.index(i, offsetBy: distance, limitedBy: limit) else { return nil }
|
|
precondition(j >= startIndex && j <= endIndex, "Index out of bounds")
|
|
return j
|
|
}
|
|
|
|
public func distance(from start: Index, to end: Index) -> Int {
|
|
precondition(start >= startIndex && start <= endIndex, "Index out of bounds")
|
|
precondition(end >= startIndex && end <= endIndex, "Index out of bounds")
|
|
return _base.distance(from: start, to: end)
|
|
}
|
|
|
|
public subscript(position: Index) -> Character {
|
|
precondition(position >= startIndex && position < endIndex, "Index out of bounds")
|
|
return _base[position]
|
|
}
|
|
|
|
public subscript(bounds: Range<Index>) -> Self {
|
|
precondition(
|
|
bounds.lowerBound >= startIndex && bounds.upperBound <= endIndex,
|
|
"Range out of bounds")
|
|
return Self(_base, in: bounds)
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring {
|
|
public func index(roundingDown i: Index) -> Index {
|
|
precondition(i >= startIndex && i <= endIndex, "Index out of bounds")
|
|
return _base.index(roundingDown: i)
|
|
}
|
|
|
|
public func index(roundingUp i: Index) -> Index {
|
|
precondition(i >= startIndex && i <= endIndex, "Index out of bounds")
|
|
return _base.index(roundingUp: i)
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring {
|
|
/// Run the closure `body` to mutate the contents of this view within `range`, then update
|
|
/// the bounds of this view to maintain an approximation of their logical position in the
|
|
/// resulting string.
|
|
///
|
|
/// The `range` argument is validated to be within the original bounds of the substring.
|
|
internal mutating func _mutateBasePreservingBounds<R>(
|
|
in range: Range<Index>,
|
|
with body: (inout BigString) -> R
|
|
) -> R {
|
|
precondition(
|
|
range.lowerBound >= _bounds.lowerBound && range.upperBound <= _bounds.upperBound,
|
|
"Range out of bounds")
|
|
|
|
let startOffset = self.startIndex.utf8Offset
|
|
let endOffset = self.endIndex.utf8Offset
|
|
let oldCount = self._base._utf8Count
|
|
|
|
defer {
|
|
// Substring mutations may change grapheme boundaries across the bounds of the original
|
|
// substring value, and we need to ensure that the substring's bounds remain well-aligned.
|
|
// Unfortunately, there are multiple ways of doing this, none of which are obviously
|
|
// superior to others. To keep the behavior easier to explan, we emulate substring
|
|
// initialization and round the start and end indices down to the nearest Character boundary
|
|
// after each mutation.
|
|
let delta = self._base._utf8Count - oldCount
|
|
let start = _base.index(roundingDown: Index(_utf8Offset: startOffset))
|
|
let end = _base.index(roundingDown: Index(_utf8Offset: endOffset + delta))
|
|
self._bounds = start ..< end
|
|
}
|
|
return body(&self._base)
|
|
}
|
|
}
|
|
|
|
@available(SwiftStdlib 6.2, *)
|
|
extension BigSubstring: RangeReplaceableCollection {
|
|
public init() {
|
|
let str = BigString()
|
|
let bounds = Range(uncheckedBounds: (str.startIndex, str.endIndex))
|
|
self.init(_unchecked: str, in: bounds)
|
|
}
|
|
|
|
public mutating func reserveCapacity(_ n: Int) {
|
|
// Do nothing.
|
|
}
|
|
|
|
public mutating func replaceSubrange( // Note: Sequence, not Collection
|
|
_ subrange: Range<Index>,
|
|
with newElements: __owned some Sequence<Character>
|
|
) {
|
|
_mutateBasePreservingBounds(in: subrange) {
|
|
$0.replaceSubrange(subrange, with: newElements)
|
|
}
|
|
}
|
|
|
|
public init(_ elements: some Sequence<Character>) {
|
|
let base = BigString(elements)
|
|
self.init(base, in: base.startIndex ..< base.endIndex)
|
|
}
|
|
|
|
public init(repeating repeatedValue: Character, count: Int) {
|
|
self.init(BigString(repeating: repeatedValue, count: count))
|
|
}
|
|
|
|
public init(repeating repeatedValue: some StringProtocol, count: Int) {
|
|
self.init(BigString(repeating: repeatedValue, count: count))
|
|
}
|
|
|
|
public init(repeating repeatedValue: BigString, count: Int) {
|
|
self.init(BigString(repeating: repeatedValue, count: count))
|
|
}
|
|
|
|
public init(repeating repeatedValue: BigSubstring, count: Int) {
|
|
self.init(BigString(repeating: repeatedValue, count: count))
|
|
}
|
|
|
|
public mutating func append(_ newElement: Character) {
|
|
let i = endIndex
|
|
_mutateBasePreservingBounds(in: i ..< i) {
|
|
$0.insert(newElement, at: i)
|
|
}
|
|
}
|
|
|
|
public mutating func append(contentsOf newElements: __owned some Sequence<Character>) {
|
|
let i = endIndex
|
|
_mutateBasePreservingBounds(in: i ..< i) {
|
|
$0.insert(contentsOf: newElements, at: i)
|
|
}
|
|
}
|
|
|
|
public mutating func insert(_ newElement: Character, at i: Index) {
|
|
_mutateBasePreservingBounds(in: i ..< i) {
|
|
$0.insert(newElement, at: i)
|
|
}
|
|
}
|
|
|
|
public mutating func insert(
|
|
contentsOf newElements: __owned some Sequence<Character>, // Note: Sequence, not Collection
|
|
at i: Index
|
|
) {
|
|
_mutateBasePreservingBounds(in: i ..< i) {
|
|
$0.insert(contentsOf: newElements, at: i)
|
|
}
|
|
}
|
|
|
|
@discardableResult
|
|
public mutating func remove(at i: Index) -> Character {
|
|
let j = self.index(after: i)
|
|
return _mutateBasePreservingBounds(in: i ..< j) {
|
|
$0.remove(at: i)
|
|
}
|
|
}
|
|
|
|
public mutating func removeSubrange(_ bounds: Range<Index>) {
|
|
_mutateBasePreservingBounds(in: bounds) {
|
|
$0.removeSubrange(bounds)
|
|
}
|
|
}
|
|
|
|
public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
|
|
let bounds = self._bounds
|
|
_mutateBasePreservingBounds(in: bounds) {
|
|
$0.removeSubrange(bounds)
|
|
}
|
|
assert(_bounds.isEmpty)
|
|
}
|
|
}
|
|
|
|
#endif // compiler(>=6.2) && !$Embedded
|