1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2017 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
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// @opaque
internal final class _StringBreadcrumbs {
/// The distance between successive breadcrumbs, measured in UTF-16 code
/// units.
internal static var breadcrumbStride: Int { 64 }
internal var utf16Length: Int
// TODO: does this need to be a pair?.... Can we be smaller than Int?
internal var crumbs: [String.Index]
// TODO: Does this need to be inout, unique, or how will we be enforcing
// atomicity?
internal init(_ str: String) {
let stride = _StringBreadcrumbs.breadcrumbStride
self.crumbs = []
if str.isEmpty {
self.utf16Length = 0
return
}
self.crumbs.reserveCapacity(
(str._guts.count / 3) / stride)
// TODO(String performance): More efficient implementation of initial scan.
// We'll also want to benchmark this initial scan in order to track changes.
let utf16 = str.utf16
var i = 0
var curIdx = utf16.startIndex
while curIdx != utf16.endIndex {
if i % stride == 0 { //i.isMultiple(of: stride) {
self.crumbs.append(curIdx)
}
i = i &+ 1
curIdx = utf16.index(after: curIdx)
}
// Corner case: index(_:offsetBy:) can produce the endIndex
if i % stride == 0 {
self.crumbs.append(utf16.endIndex)
}
self.utf16Length = i
_internalInvariant(self.crumbs.count == 1 + (self.utf16Length / stride))
_invariantCheck(for: str)
}
}
extension _StringBreadcrumbs {
internal var stride: Int {
@inline(__always) get { return _StringBreadcrumbs.breadcrumbStride }
}
// Fetch the lower-bound index corresponding to the given offset, returning
// the index and the remaining offset to adjust
internal func getBreadcrumb(
forOffset offset: Int
) -> (lowerBound: String.Index, remaining: Int) {
return (crumbs[offset / stride], offset % stride)
}
// Fetch the lower-bound offset corresponding to the given index, returning
// the lower-bound and its offset
internal func getBreadcrumb(
forIndex idx: String.Index
) -> (lowerBound: String.Index, offset: Int) {
var lowerBound = idx._encodedOffset / 3 / stride
var upperBound = Swift.min(1 + (idx._encodedOffset / stride), crumbs.count)
_internalInvariant(crumbs[lowerBound] <= idx)
_internalInvariant(upperBound == crumbs.count || crumbs[upperBound] >= idx)
while (upperBound &- lowerBound) > 1 {
let mid = lowerBound + ((upperBound &- lowerBound) / 2)
if crumbs[mid] <= idx { lowerBound = mid } else { upperBound = mid }
}
let crumb = crumbs[lowerBound]
_internalInvariant(crumb <= idx)
_internalInvariant(lowerBound == crumbs.count-1 || crumbs[lowerBound+1] > idx)
return (crumb, lowerBound &* stride)
}
#if !INTERNAL_CHECKS_ENABLED
@nonobjc @inline(__always) internal func _invariantCheck(for str: String) {}
#else
@nonobjc @inline(never) @_effects(releasenone)
internal func _invariantCheck(for str: String) {
_internalInvariant(self.utf16Length == str.utf16._distance(
from: str.startIndex, to: str.endIndex),
"Stale breadcrumbs")
}
#endif // INTERNAL_CHECKS_ENABLED
}
|
