Swift探索（十一）: String源码分析

一：String 的内存布局

1. String 源码分析

在 Swift源码中找到 String.swift 文件并定位到 String 的定义。

@frozen
public struct String {
  public // @SPI(Foundation)
  var _guts: _StringGuts

  @inlinable @inline(__always)
  internal init(_ _guts: _StringGuts) {
    self._guts = _guts
    _invariantCheck()
  }

  // This is intentionally a static function and not an initializer, because
  // an initializer would conflict with the Int-parsing initializer, when used
  // as function name, e.g.
  //   [1, 2, 3].map(String.init)
  @_alwaysEmitIntoClient
  @_semantics("string.init_empty_with_capacity")
  @_semantics("inline_late")
  @inlinable
  internal static func _createEmpty(withInitialCapacity: Int) -> String {
    return String(_StringGuts(_initialCapacity: withInitialCapacity))
  }

  /// Creates an empty string.
  ///
  /// Using this initializer is equivalent to initializing a string with an
  /// empty string literal.
  ///
  ///     let empty = ""
  ///     let alsoEmpty = String()
  @inlinable @inline(__always)
  @_semantics("string.init_empty")
  public init() { self.init(_StringGuts()) }
}

通过源码可以发现 String 的本质是一个结构体，并且有一个 _StringGuts 类型的成员变量 _guts 。在初始化的时候需要传入 _StringGuts 类型的参数。接着找到 StringGuts.swift 文件，并定位到 _StringGuts 的定义。

struct _StringGuts: @unchecked Sendable {
  @usableFromInline
  internal var _object: _StringObject

  @inlinable @inline(__always)
  internal init(_ object: _StringObject) {
    self._object = object
    _invariantCheck()
  }

  // Empty string
  @inlinable @inline(__always)
  init() {
    self.init(_StringObject(empty: ()))
  }
}

可以发现 _StringGuts 也是一个结构体，并且遵守了协议 Sendable ，有一个 _StringObject 类型的成员变量 _object，并且初始化的时候需要传入 _StringObject 类型的参数。接着找到 StringObject.swift 文件，并定位到 _StringObject 的定义。

@frozen @usableFromInline
internal struct _StringObject {
  // Namespace to hold magic numbers
  @usableFromInline @frozen
  enum Nibbles {}

  // Abstract the count and performance-flags containing word
  @frozen @usableFromInline
  struct CountAndFlags {
    @usableFromInline
    var _storage: UInt64

    @inlinable @inline(__always)
    internal init(zero: ()) { self._storage = 0 }
  }

#if arch(i386) || arch(arm) || arch(arm64_32) || arch(wasm32)
  @usableFromInline @frozen
  internal enum Variant {
    case immortal(UInt)
    case native(AnyObject)
    case bridged(_CocoaString)

    @inlinable @inline(__always)
    internal static func immortal(start: UnsafePointer<UInt8>) -> Variant {
      let biased = UInt(bitPattern: start) &- _StringObject.nativeBias
      return .immortal(biased)
    }

    @inlinable @inline(__always)
    internal var isImmortal: Bool {
      if case .immortal = self { return true }
      return false
    }
  }

  @usableFromInline
  internal var _count: Int

  @usableFromInline
  internal var _variant: Variant

  @usableFromInline
  internal var _discriminator: UInt8

  @usableFromInline
  internal var _flags: UInt16

  @inlinable @inline(__always)
  init(count: Int, variant: Variant, discriminator: UInt64, flags: UInt16) {
    _internalInvariant(discriminator & 0xFF00_0000_0000_0000 == discriminator,
      "only the top byte can carry the discriminator and small count")

    self._count = count
    self._variant = variant
    self._discriminator = UInt8(truncatingIfNeeded: discriminator &>> 56)
    self._flags = flags
    self._invariantCheck()
  }

  @inlinable @inline(__always)
  init(variant: Variant, discriminator: UInt64, countAndFlags: CountAndFlags) {
    self.init(
      count: countAndFlags.count,
      variant: variant,
      discriminator: discriminator,
      flags: countAndFlags.flags)
  }

  @inlinable @inline(__always)
  internal var _countAndFlagsBits: UInt64 {
    let rawBits = UInt64(truncatingIfNeeded: _flags) &<< 48
                | UInt64(truncatingIfNeeded: _count)
    return rawBits
  }
#else

  //
  // Laid out as (_countAndFlags, _object), which allows small string contents
  // to naturally start on vector-alignment.
  //

  @usableFromInline
  internal var _countAndFlagsBits: UInt64

  @usableFromInline
  internal var _object: Builtin.BridgeObject

  @inlinable @inline(__always)
  internal init(zero: ()) {
    self._countAndFlagsBits = 0
    self._object = Builtin.valueToBridgeObject(UInt64(0)._value)
  }

#endif

  @inlinable @inline(__always)
  internal var _countAndFlags: CountAndFlags {
    _internalInvariant(!isSmall)
    return CountAndFlags(rawUnchecked: _countAndFlagsBits)
  }
}

我们可以看到 _StringObject 也是一个结构体，并且有 4 个成员变量分别是

_count : Int 类型
_variant : variant 类型
_discriminator : UInt8 类型
_flags : UInt16类型
在 _StringGuts 的定义中能够看见空字符串创建时调用了 _StringObject 的 empty:() 函数，那么找到这个函数的定义

extension _StringObject {
  @inlinable @inline(__always)
  internal init(_ small: _SmallString) {
    // Small strings are encoded as _StringObjects in reverse byte order
    // on big-endian platforms. This is to match the discriminator to the
    // spare bits (the most significant nibble) in a pointer.
    let word1 = small.rawBits.0.littleEndian
    let word2 = small.rawBits.1.littleEndian
#if arch(i386) || arch(arm) || arch(arm64_32) || arch(wasm32)
    // On 32-bit, we need to unpack the small string.
    let smallStringDiscriminatorAndCount: UInt64 = 0xFF00_0000_0000_0000

    let leadingFour = Int(truncatingIfNeeded: word1)
    let nextFour = UInt(truncatingIfNeeded: word1 &>> 32)
    let smallDiscriminatorAndCount = word2 & smallStringDiscriminatorAndCount
    let trailingTwo = UInt16(truncatingIfNeeded: word2)
    self.init(
      count: leadingFour,
      variant: .immortal(nextFour),
      discriminator: smallDiscriminatorAndCount,
      flags: trailingTwo)
#else
    // On 64-bit, we copy the raw bits (to host byte order).
    self.init(rawValue: (word1, word2))
#endif
    _internalInvariant(isSmall)
  }

  @inlinable
  internal static func getSmallCount(fromRaw x: UInt64) -> Int {
    return Int(truncatingIfNeeded: (x & 0x0F00_0000_0000_0000) &>> 56)
  }

  @inlinable @inline(__always)
  internal var smallCount: Int {
    _internalInvariant(isSmall)
    return _StringObject.getSmallCount(fromRaw: discriminatedObjectRawBits)
  }

  @inlinable
  internal static func getSmallIsASCII(fromRaw x: UInt64) -> Bool {
    return x & 0x4000_0000_0000_0000 != 0
  }
  @inlinable @inline(__always)
  internal var smallIsASCII: Bool {
    _internalInvariant(isSmall)
    return _StringObject.getSmallIsASCII(fromRaw: discriminatedObjectRawBits)
  }

  @inlinable @inline(__always)
  internal init(empty:()) {
    // Canonical empty pattern: small zero-length string
#if arch(i386) || arch(arm) || arch(arm64_32) || arch(wasm32)
    self.init(
      count: 0,
      variant: .immortal(0),
      discriminator: Nibbles.emptyString,
      flags: 0)
#else
    self._countAndFlagsBits = 0
    self._object = Builtin.valueToBridgeObject(Nibbles.emptyString._value)
#endif
    _internalInvariant(self.smallCount == 0)
    _invariantCheck()
  }
}

在 _StringObject 的扩展中可以找到 empty:() 函数的定义，能够看到这里区分了架构，对于我们来说只需要看第一个分支就可以了，发现这里调用了一个方法 count: variant: discriminator: flags:，找到这个方法的定义

@inlinable @inline(__always)
  init(count: Int, variant: Variant, discriminator: UInt64, flags: UInt16) {
    _internalInvariant(discriminator & 0xFF00_0000_0000_0000 == discriminator,
      "only the top byte can carry the discriminator and small count")

    self._count = count
    self._variant = variant
    self._discriminator = UInt8(truncatingIfNeeded: discriminator &>> 56)
    self._flags = flags
    self._invariantCheck()
  }

可以看见这里就是在对 _StringObject 的成员变量进行赋值操作。那么这几个成员变量分别代表着什么意思呢？

1.1 _count

_count 是 Int 类型，从字面意思其实也不难理解就是字符串大小的意思

1.2 _variant

_variant 是 Variant 类型找到 Variant 的定义

internal enum Variant {
    case immortal(UInt)
    case native(AnyObject)
    case bridged(_CocoaString)

可以看见 Variant 是一个枚举类型，代表着字符串的三种情况，分别为 immortal、native 以及 bridged 。而通过刚才初始化方法的传值，此时的 _variant 类型是 .immortal(0) 类型的，这个代表 Swift 原生的字符串类型。native 着代表着 AnyObject 。bridged 代表着 _CocoaString 也就是 NSString 。

1.3 _discriminator

_discriminator 是 UInt8 类型，在初始化方法中我们发现传入了 Nibbles.emptyString 值，定位到 Nibbles 的定义

enum Nibbles {}

发现这是一个什么 case 都没有的枚举，但是在 StringObject.swift 文件的下面还有一些 Nibbles 的扩展

extension _StringObject.Nibbles {
  // The canonical empty string is an empty small string
  @inlinable @inline(__always)
  internal static var emptyString: UInt64 {
    return _StringObject.Nibbles.small(isASCII: true)
  }
}

extension _StringObject.Nibbles {
  // Mask for address bits, i.e. non-discriminator and non-extra high bits
  @inlinable @inline(__always)
  static internal var largeAddressMask: UInt64 { return 0x0FFF_FFFF_FFFF_FFFF }

  // Mask for address bits, i.e. non-discriminator and non-extra high bits
  @inlinable @inline(__always)
  static internal var discriminatorMask: UInt64 { return ~largeAddressMask }
}

extension _StringObject.Nibbles {
  // Discriminator for small strings
  @inlinable @inline(__always)
  internal static func small(isASCII: Bool) -> UInt64 {
    return isASCII ? 0xE000_0000_0000_0000 : 0xA000_0000_0000_0000
  }

  // Discriminator for small strings
  @inlinable @inline(__always)
  internal static func small(withCount count: Int, isASCII: Bool) -> UInt64 {
    _internalInvariant(count <= _SmallString.capacity)
    return small(isASCII: isASCII) | UInt64(truncatingIfNeeded: count) &<< 56
  }

  // Discriminator for large, immortal, swift-native strings
  @inlinable @inline(__always)
  internal static func largeImmortal() -> UInt64 {
    return 0x8000_0000_0000_0000
  }

  // Discriminator for large, mortal (i.e. managed), swift-native strings
  @inlinable @inline(__always)
  internal static func largeMortal() -> UInt64 { return 0x0000_0000_0000_0000 }

  internal static func largeCocoa(providesFastUTF8: Bool) -> UInt64 {
    return providesFastUTF8 ? 0x4000_0000_0000_0000 : 0x5000_0000_0000_0000
  }
}

可以在第一个扩展中找到 emptyString 返回的是 Nibbles 的 small(isASCII:) 方法，true 代表是 ASCII，false 代表不是。在第三个扩展中我们看到 small(isASCII: Bool) 方法的实现，当是 ASCII 码的时候返回的是 0xE000_0000_0000_0000，当不是 ASCII 码的时候返回的是 0xA000_0000_0000_0000

1.4 小字符串

对于空字符串通过上面的源码能够得到 _discriminator 的值应该是 0xE000_0000_0000_0000 接下来验证一下

空字符串.png

此时看到当前的字符串打印出来属于 0xE000_0000_0000_0000，这个空字符串属于 ASCII，这与源码一致。
我们知道中文字符不是 ASCII 码，那么将字符串赋值中文，那么这里是否会打印 0xA000_0000_0000_0000 呢？我们来试一下。

中文字符串.png

能够发现这里打印的就是 0xA000_0000_0000_0000 这与我们猜想的一致。那 0xa 后面的 6 是什么意思? 前面的 0x0000bda5e5a882e6 又是什么？
这里为了方法观察，将字符串赋值成英文字符。

aa字符串.png

将字符串赋值成 aa 后，能够发现第一个 8 字节存储的是 0x0000000000006161，而我们知道 a 的 ASCII 的值是 97，而 97 的 16 进制就是 61 ，而 0xe 后面的值是 2，是不是就代表着 _count ？接着试一试 abc

abc.png

字符串是 abc 的时候，第一个 8 字节存储的正是 abc 所对应的 ASCII 码的 16 进制。并且 0xe 后面这时已经变成了 3 。我们知道字符串的大小是 16 字节，那么对于小字符串 (长度小于 16 ) 它的值是否就直接存储在这 16 字节中？

abcdefghijklmno.png

我们可以看到字符串的长度为 15 时刚好占满这 16 字节。

1.5 大字符串

那对于长度超过 15 的大字符串，这又是怎么存储的呢？

abcdefghijklmnopq.png

我们可以看到当字符串的长度大于 15 的时候这里的存储内容就发生了变化，第二个 8 字节变成了 0x8 开头，这是找到源码中的 0x8000000000000000

extension _StringObject.Nibbles {
  // Discriminator for small strings
  @inlinable @inline(__always)
  internal static func small(isASCII: Bool) -> UInt64 {
    return isASCII ? 0xE000_0000_0000_0000 : 0xA000_0000_0000_0000
  }

  // Discriminator for small strings
  @inlinable @inline(__always)
  internal static func small(withCount count: Int, isASCII: Bool) -> UInt64 {
    _internalInvariant(count <= _SmallString.capacity)
    return small(isASCII: isASCII) | UInt64(truncatingIfNeeded: count) &<< 56
  }

  // Discriminator for large, immortal, swift-native strings
  @inlinable @inline(__always)
  internal static func largeImmortal() -> UInt64 {
    return 0x8000_0000_0000_0000
  }

  // Discriminator for large, mortal (i.e. managed), swift-native strings
  @inlinable @inline(__always)
  internal static func largeMortal() -> UInt64 { return 0x0000_0000_0000_0000 }

  internal static func largeCocoa(providesFastUTF8: Bool) -> UInt64 {
    return providesFastUTF8 ? 0x4000_0000_0000_0000 : 0x5000_0000_0000_0000
  }
}

可以看到这里的 largeImmortal() 方法返回的是 0x8000_0000_0000_0000 代表着原生字符串的大字符串

extension _StringObject {
  @inlinable @inline(__always)
  internal init(immortal bufPtr: UnsafeBufferPointer<UInt8>, isASCII: Bool) {
    let countAndFlags = CountAndFlags(
      immortalCount: bufPtr.count, isASCII: isASCII)
#if arch(i386) || arch(arm) || arch(arm64_32) || arch(wasm32)
    self.init(
      variant: .immortal(start: bufPtr.baseAddress._unsafelyUnwrappedUnchecked),
      discriminator: Nibbles.largeImmortal(),
      countAndFlags: countAndFlags)
#else
    // We bias to align code paths for mortal and immortal strings
    let biasedAddress = UInt(
      bitPattern: bufPtr.baseAddress._unsafelyUnwrappedUnchecked
    ) &- _StringObject.nativeBias

    self.init(
      pointerBits: UInt64(truncatingIfNeeded: biasedAddress),
      discriminator: Nibbles.largeImmortal(),
      countAndFlags: countAndFlags)
#endif
  }
...
}

largeImmortal() 方法在初始化的时候调用，并且将 largeImmortal() 的返回值赋值给了_discriminator , 这与我们之前研究小字符串时的逻辑是一致的。
那么0xd000000000000011 和 0x0000000100003f60 这两个地址又是什么呢？

1.5.1 前 8 字节

0xd000000000000011 这个存储的到底是什么呢？
在上面的初始化方法中我们看到调用的是 self.init(variant: discriminator: countAndFlags:) 这个初始化方法，这个传了一个参数叫做 countAndFlags 并且 countAndFlags 等于 CountAndFlags( immortalCount: bufPtr.count, isASCII: isASCII) 定位到 CountAndFlags 的初始化方法 immortalCount: isASCII:

extension _StringObject.CountAndFlags {
  ...

  //
  // Specialized initializers
  //
  @inlinable @inline(__always)
  internal init(immortalCount: Int, isASCII: Bool) {
    self.init(
      count: immortalCount,
      isASCII: isASCII,
      isNFC: isASCII,
      isNativelyStored: false,
      isTailAllocated: true)
  }
  ...

在这里找到了这个方法的定义。我们注意到这个 _StringObject.CountAndFlags 扩展的上方有着苹果官方留下的注释

CountAndFlags.png

通过阅读这个注释，我们了解到

isASCII ：用来判断当前字符串是否是 ASCII，在高 63 位。
isNFC ：这个默认为 1，在高 62 位。
isNativelyStored ：是否是原生存储，在高 61 位。
isTailAllocated ：是否是尾部分配的，在高 60 位。
TBD ：留作将来使用，在高 59 位到高 48 位。
count ：当前字符串的大小，在高 47 位到低 0 位。
利用苹果电脑的计算器(程序员型) 来看一下 0xd000000000000011

0xd000000000000011.png

高 4 位 1101 与代码和注释一致，那么 16 进制的 0x11 的 10 进制就是 17 而我们的字符串是 abcdefghijklmnopq 正好 17 个所以大字符串的前 8 位地址存储的是 countAndFlags

1.5.2 后 8 字节

0x8000000100003f60 对与后 8 字节之前已经知道了 0x8000_0000_0000_0000 代表着大原生字符串。那么后面的 0x100003f60 代表着什么呢？通过源码找到了苹果留下的另一段注释

image.png

通过官方的注释得知大字符串可以是原生的、共享的或者是外来的。我们这里主要探究原生的字符串。根据官方的注释，这个原生的字符串具有尾部分配 ( tail-allocated ) 的存储空间，它从存储对象地址的 nativeBias 偏移量开始。这个偏移量是 32。通过前 8 字节的分析我们得到 isTailAllocated 是 1 ，这里也就和前面我们分析的相呼应。
接下来看一下 discriminator（鉴别器）和 objectAddr 的地址分配方式，根据官方给的注释，这个 discriminator 在后 8 字节中，占据的位置是高 63 位到高 60 位。高 60 位到低 0 位存储的就是这个额外的存储空间的内存地址。
这个 objectAddr 存储的是这个额外的存储空间的内存地址，但是它是一个相对地址，因为它需要加上 nativeBias，得到的才是这个额外的存储空间的地址值。
那也就是意味着当字符串是大字符串的时候，会分配额外的存储空间，用这个额外的存储空间存储字符串的值。
那么对于 0x100003f60 这个地址来说就是 objectAddr , 这个地址再偏移 32 位得到的地址就是存储字符串的值的地址。
0x100003f60 + 32 = 0x100003f60 + 0x20 = 0x100003f80

0x100003f80.png

1.6 String的内存结构总结

一个 String 变量/常量的大小为 16 个字节。
当字符串的大小小于等于 15 的时候为小字符串，当字符串的大小大于 15 的时候为大字符串。
小字符串时，前 15 个字节用来存储字符串的值，最后一个字节记录当前字符串是否是 ASCII 和字符串的大小 count。
大字符串时，前 8 个字节用来记录字符串的大小和其它的一些信息 countAndFlags，比如是否是 ASCII。后 8 个字节中，高 63 位到高 60 位存储的是鉴别器( discriminator )的值，剩余的用来存储相对偏移地址( objectAddr )，这个地址需要再偏移 32 位才是存储字符串的值的地址。

二. String.index

在 Swift 中对于 String 我们想要访问到某一个字符可以通过 Index 去获取

let string = "大家好"
// 从开始位置向后偏移1，返回结果是String.Index类型
let index = string.index(string.startIndex, offsetBy: 1);
print(string[index]);

这里能够通过 string[index] 这样的方式去获取一个字符，那么为什么不能像数组那样直接传入一个数字而且必须要传入一个 Swift.Index 类型呢?

string[1].png

2.1 Swift 中 String 的本质

Swift 中的 String 代表的是一系列的 characters（字符），字符的表示方式有很多种，比如我们最熟悉的 ASCII 码，ASCII 码一共规定了 128 个字符的编码，对于英文字符来说 128 个字符已经够用了，但是相对于其他语言来说，这是远远不够用的，比如中国汉字。这也就意味着不同国家不同语言都需要有自己的编码格式，这个时候同一个二进制文件就有可能被翻译成不同的字符。

有一种编码能够把所有的符号都纳入其中的方式，就是我们熟悉的 Unicode。但是 Unicode 只是规定了符号对应的二进制代码，并没有详细明确这个二进制代码应该如何存储。

比如 "大家好hello" 对应的 Unicode 编码以及转成二进制的结果如下

大  5927  0101 1001 0010 0111
家  5bb6  0101 1011 1011 0110
好  597d  0101 1001 0111 1101
h  0068  0000 0000 0110 1000
e  0065  0000 0000 0110 0101
l  006c  0000 0000 0110 1100
l  006c  0000 0000 0110 1100
o  006f  0000 0000 0110 1111

对于英文字符如果统一采用中文字符这种方式去存储，也就是用和中文字符一样的步长去存储英文字符，必然会有很大的浪费(前 8 位必为 0 )。

为了解决这个问题，就可以用 UTF-8，UTF-8 最大的一个特点，就是它是一种变长的编码方式。它可以使用 1~4 个字节表示一个符号，根据不同的符号而变化字节长度。这里简单说一下 UTF-8 的规则：

1. 单字节的字符，字节的第一位设为 0，对于英语文本，UTF-8 码只占用一个字节，和 ASCII 码完全相同;
1. n 个字节的字符( n>1 )，第一个字节的前 n 位设为 1 ，第 n+1 位设为 0，后面字节的前两位都设为 10 ，这 n 个字节的其余空位填充该字符 Unicode 码，高位用 0 补足。

大  11100101 10100100 10100111
家  11100101 10101110 10110110
好  11100101 10100101 10111101
h  0110 1000
e  0110 0101
l  0110 1100
l  0110 1100
o  0110 1111

对于 Swift 来说， String 是一系列字符的集合，也就意味着 String 中的每一个元素是不等⻓的。就是说在进行内存移动的时候步⻓是不一样的。这里和 Array 数组不一样，当我们遍历数组中的元素的时候，因为每个元素的内存大小是一致的，所以每次的偏移量就是数组元素的内存大小( Int 类型就偏移 8 字节)。
但是对于 String 来说如果我要访问 string[1] 那么是不是要把 "大" 这个字段遍历完成之后才能够确定 "家" 的偏移量? 依次内推每一次都要重新遍历计算偏移量，这个时候无疑增加了很多的内存消耗。这就是为什么不能通过 Int 作为下标来去访问 String。

2.2 Swift.Index 的本质

来到源码中关于 String 的 Index 布局的描述

Index的描述.png

从注释中我们大致明白了上述表示的意思：

position aka encodedOffset ：一个 48 bit 值，用来记录码位偏移量。
transcoded offset : 一个 2 bit 的值，用来记录字符使用的码位数量。
grapheme cache : 一个 6 bit 的值，用来记录下一个字符的边界。
reserved : 7 bit 的预留字段
scalar aligned : 一个 1 bit 的值，用来记录标量是否已经对齐过。

所以对于 String 的 Index 的本质是存储了 encodedOffset 和 transcoded offset。当我们构建 String 的 Index 的时候，其实是把 encodedOffset 和 transcoded offset 计算出来存放到 Index 的内存信息里面。而这个 Index 本身就是一个 64 位的位域信息。