0%

【Go语言设计与实现】String

字符串是 Go 语言中最常用的基础数据类型之一,虽然字符串往往被看做一个整体,但是实际上字符串是一片连续的内存空间,我们也可以将它理解成一个由字符组成的数组,在这一节中就会详细介绍字符串的实现原理、相关转换过程以及常见操作的实现。

字符串虽然在 Go 语言中是基本类型 string,但是它实际上是由字符组成的数组,C 语言中的字符串就使用字符数组 char[] 表示,作为数组会占用一片连续的内存空间,这片内存空间存储了的字节共同组成了字符串,Go 语言中的字符串其实是一个只读的字节数组,下图展示了 "hello" 字符串在内存中的存储方式:

in-memory-string

图 3-18 内存中的字符串

如果是代码中存在的字符串,会在编译期间被标记成只读数据 SRODATA 符号,假设我们有以下的一段代码,其中包含了一个字符串,当我们将这段代码编译成汇编语言时,就能够看到 hello 字符串有一个 SRODATA 的标记:

1
2
3
4
5
6
7
8
9
10
11
12
13
$ cat main.go
package main

func main() {
str := "hello"
println([]byte(str))
}

$ GOOS=linux GOARCH=amd64 go tool compile -S main.go
...
go.string."hello" SRODATA dupok size=5
0x0000 68 65 6c 6c 6f hello
...

只读只意味着字符串会分配到只读的内存空间并且这块内存不会被修改,但是在运行时我们其实还是可以将这段内存拷贝到堆或者栈上,将变量的类型转换成 []byte 之后就可以进行,修改后通过类型转换就可以变回 string,Go 语言只是不支持直接修改 string 类型变量的内存空间。

数据结构

字符串在 Go 语言中的接口其实非常简单,每一个字符串在运行时都会使用如下的 StringHeader 结构体表示,在运行时包的内部其实有一个私有的结构 stringHeader,它有着完全相同的结构只是用于存储数据的 Data 字段使用了 unsafe.Pointer 类型:

1
2
3
4
type StringHeader struct {
Data uintptr
Len int
}

我们会经常会说字符串是一个只读的切片类型,这是因为切片在 Go 语言的运行时表示与字符串高度相似:

1
2
3
4
5
type SliceHeader struct {
Data uintptr
Len int
Cap int
}

与切片的结构体相比,字符串少了一个表示容量的 Cap 字段,因为字符串作为只读的类型,我们并不会直接向字符串直接追加元素改变其本身的内存空间,所有在字符串上执行的写入操作实际都是通过拷贝实现的。

解析过程

字符串的解析一定是解析器在词法分析时就完成的,词法分析阶段会对源文件中的字符串进行切片和分组,将原有无意义的字符流转换成 Token 序列,在 Go 语言中,有两种字面量方式可以声明一个字符串,一种是使用双引号,另一种是使用反引号:

1
2
3
str1 := "this is a string"
str2 := `this is another
string`

使用双引号声明的字符串和其他语言中的字符串没有太多的区别,它只能用于单行字符串的初始化,如果字符串内部出现双引号,需要使用 \ 符号避免编译器的解析错误,而反引号声明的字符串就可以摆脱单行的限制,因为双引号不再负责标记字符串的开始和结束,我们可以在字符串内部直接使用 ",在遇到需要手写 JSON 或者其他复杂数据格式的场景下非常方便。

1
json := `{"author": "draven", "tags": ["golang"]}`

两种不同的声明方式其实也意味着 Go 语言的编译器需要在解析的阶段能够区分并且正确解析这两种不同的字符串格式,解析字符串使用的 scanner 扫描器,它的功能就是将输入的字符流转换成 Token 流,cmd/compile/internal/syntax.scanner.stdString 方法就是它用来解析使用双引号包裹的标准字符串:

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
func (s *scanner) stdString() {
s.startLit()
for {
r := s.getr()
if r == '"' {
break
}
if r == '\\' {
s.escape('"')
continue
}
if r == '\n' {
s.ungetr()
s.error("newline in string")
break
}
if r < 0 {
s.errh(s.line, s.col, "string not terminated")
break
}
}
s.nlsemi = true
s.lit = string(s.stopLit())
s.kind = StringLit
s.tok = _Literal
}

从这个方法的实现我们能分析出 Go 语言处理标准字符串的逻辑:

  1. 标准字符串使用双引号表示开头和结尾;
  2. 标准字符串中需要使用反斜杠 \escape 双引号;
  3. 标准字符串中不能出现如下所示的隐式换行符号 \n
1
2
str := "start
end"

使用反引号声明的原始字符串的解析规则就非常简单了,cmd/compile/internal/syntax.scanner.rawString 会将非反引号的所有字符都划分到当前字符串的范围中,所以我们可以使用它来支持复杂的多行字符串:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func (s *scanner) rawString() {
s.startLit()
for {
r := s.getr()
if r == '`' {
break
}
if r < 0 {
s.errh(s.line, s.col, "string not terminated")
break
}
}
s.nlsemi = true
s.lit = string(s.stopLit())
s.kind = StringLit
s.tok = _Literal
}

无论是标准字符串还是原始字符串最终都会被标记成 StringLit 类型的 Token 并传递到编译的下一个阶段 — 语法分析,在语法分析阶段,与字符串相关的表达式都会使用如下的方法 cmd/compile/internal/gc.noder.basicLit 处理:

1
2
3
4
5
6
7
8
9
10
func (p *noder) basicLit(lit *syntax.BasicLit) Val {
switch s := lit.Value; lit.Kind {
case syntax.StringLit:
if len(s) > 0 && s[0] == '`' {
s = strings.Replace(s, "\r", "", -1)
}
u, _ := strconv.Unquote(s)
return Val{U: u}
}
}

无论是 import 语句中包的路径、结构体中的字段标签还是表达式中的字符串都会使用这个方法将原生字符串中最后的换行符删除并对字符串 Token 进行 Unquote,也就是去掉字符串两遍的引号等无关干扰,还原其本来的面目。

strconv.Unquote 方法处理了很多边界条件导致整个函数非常复杂,不仅包括各种不同引号的处理,还包括 UTF-8 等编码的相关问题,所以在这里也就不展开介绍了。

拼接

Go 语言拼接字符串会使用 + 符号,编译器会将该符号对应的 OADD 节点转换成 OADDSTR 类型的节点,随后在 cmd/compile/internal/gc.walkexpr 函数中调用 cmd/compile/internal/gc.addstr 函数生成用于拼接字符串的代码:

1
2
3
4
5
6
7
func walkexpr(n *Node, init *Nodes) *Node {
switch n.Op {
...
case OADDSTR:
n = addstr(n, init)
}
}

cmd/compile/internal/gc.addstr 函数能帮助我们在编译期间选择合适的函数对字符串进行拼接,如果需要拼接的字符串小于或者等于 5 个,那么就会直接调用 concatstring{2,3,4,5} 等一系列函数,如果超过 5 个就会直接选择 runtime.concatstrings 传入一个数组切片。

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
func addstr(n *Node, init *Nodes) *Node {
c := n.List.Len()

buf := nodnil()
args := []*Node{buf}
for _, n2 := range n.List.Slice() {
args = append(args, conv(n2, types.Types[TSTRING]))
}

var fn string
if c <= 5 {
fn = fmt.Sprintf("concatstring%d", c)
} else {
fn = "concatstrings"

t := types.NewSlice(types.Types[TSTRING])
slice := nod(OCOMPLIT, nil, typenod(t))
slice.List.Set(args[1:])
args = []*Node{buf, slice}
}

cat := syslook(fn)
r := nod(OCALL, cat, nil)
r.List.Set(args)
...

return r
}

其实无论使用 concatstring{2,3,4,5} 中的哪一个,最终都会调用 runtime.concatstrings,该函数会先对传入的切片参数进行遍历,先过滤空字符串并计算拼接后字符串的长度。

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
func concatstrings(buf *tmpBuf, a []string) string {
idx := 0
l := 0
count := 0
for i, x := range a {
n := len(x)
if n == 0 {
continue
}
l += n
count++
idx = i
}
if count == 0 {
return ""
}
if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
return a[idx]
}
s, b := rawstringtmp(buf, l)
for _, x := range a {
copy(b, x)
b = b[len(x):]
}
return s
}

如果非空字符串的数量为 1 并且当前的字符串不在栈上就可以直接返回该字符串,不需要进行额外的任何操作。

string-concat-and-copy

图 3-19 字符串的拼接和拷贝

但是在正常情况下,运行时会调用 copy 将输入的多个字符串拷贝到目标字符串所在的内存空间中,新的字符串是一片新的内存空间,与原来的字符串也没有任何关联,一旦需要拼接的字符串非常大,拷贝带来的性能损失就是无法忽略的。

类型转换

当我们使用 Go 语言解析和序列化 JSON 等数据格式时,经常需要将数据在 string[]byte 之间来回转换,类型转换的开销并没有想象的那么小,我们经常会看到 runtime.slicebytetostring 等函数出现在火焰图1中,成为程序的性能热点。

从字节数组到字符串的转换就需要使用 runtime.slicebytetostring 函数,例如:string(bytes),该函数在函数体中会先处理两种比较常见的情况,也就是字节数组的长度为 0 或者 1,这两个情况处理起来都非常简单:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func slicebytetostring(buf *tmpBuf, b []byte) (str string) {
l := len(b)
if l == 0 {
return ""
}
if l == 1 {
stringStructOf(&str).str = unsafe.Pointer(&staticbytes[b[0]])
stringStructOf(&str).len = 1
return
}
var p unsafe.Pointer
if buf != nil && len(b) <= len(buf) {
p = unsafe.Pointer(buf)
} else {
p = mallocgc(uintptr(len(b)), nil, false)
}
stringStructOf(&str).str = p
stringStructOf(&str).len = len(b)
memmove(p, (*(*slice)(unsafe.Pointer(&b))).array, uintptr(len(b)))
return
}

处理过后会根据传入的缓冲区大小决定是否需要为新的字符串分配一片内存空间,runtime.stringStructOf 会将传入的字符串指针转换成 stringStruct 结构体指针,然后设置结构体持有的字符串指针 str 和长度 len,最后通过 memmove 将原 []byte 中的字节全部复制到新的内存空间中。

当我们想要将字符串转换成 []byte 类型时,就需要使用 runtime.stringtoslicebyte 函数,该函数的实现非常容易理解:

1
2
3
4
5
6
7
8
9
10
11
func stringtoslicebyte(buf *tmpBuf, s string) []byte {
var b []byte
if buf != nil && len(s) <= len(buf) {
*buf = tmpBuf{}
b = buf[:len(s)]
} else {
b = rawbyteslice(len(s))
}
copy(b, s)
return b
}

如果向该函数传入了缓冲区,那么它会使用传入的缓冲区存储 []byte,没有传入缓冲区时,运行时会调用 runtime.rawbyteslice 创建一个新的字节切片,copy 就会将字符串中的内容拷贝到新的 []byte 中。

string-bytes-conversion

图 3-20 字符串和字节数组的转换

字符串和 []byte 中的内容虽然一样,但是字符串的内容是只读的,我们不能通过下标或者其他形式改变其中的数据,而 []byte 中的内容是可以读写的,无论从哪种类型转换到另一种都需要对其中的内容进行拷贝,而内存拷贝的性能损耗会随着字符串和 []byte 长度的增长而增长。

小结

字符串是 Go 语言中相对来说比较简单的一种数据结构,我们在这一节中详细分析了字符串与 []byte 类型的关系,从词法分析阶段理解字符串是如何被解析的,作为只读的数据类型,我们无法改变其本身的结构,但是在做拼接和类型转换等操作时时一定要注意性能的损耗,遇到需要极致性能的场景一定要尽量减少类型转换的次数。

延伸阅读


  1. 火焰图是一种分析程序性能的手段,Flame Graphs http://www.brendangregg.com/flamegraphs.html ↩︎

在Go里面,字符串实际上是类型为byte的只读切片。

一个字符串包含了任意个byte。它并不限定Unicode,UTF-8或者任何其他预定义的编码。在内容上,它完全等价于一个类型为byte的切片。

下面是一个字符串变量,它使用\xNN这样的形式来表示一些特殊的byte。

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
const sample = "\xbd\xb2\x3d\xbc\x20\xe2\x8c\x98"
fmt.Println(sample)

// ��=� ⌘
// 这个结果和程序执行的环境有关
for i := 0; i <len(sample); i++ {
fmt.Printf("%x ", sample[i])
}

// bd b2 3d bc 20 e2 8c 98
fmt.Printf("%x\n", sample)

// bdb23dbc20e28c98
fmt.Printf("% x\n", sample)

// bd b2 3d bc 20 e2 8c 98
fmt.Printf("%q\n", sample)

// \xbd\xb2=\xbc ⌘
fmt.Printf("%+q\n", sample)

// "\xbd\xb2=\xbc \u2318"
func main() {
const placeOfInterest = `⌘`
fmt.Printf("plain string: ")
fmt.Printf("%s", placeOfInterest)
fmt.Printf("\n")

fmt.Printf("quoted string: ")
fmt.Printf("%+q", placeOfInterest)
fmt.Printf("\n")

fmt.Printf("hex bytes: ")
for i := 0; i < len(placeOfInterest); i++ {
fmt.Printf("%x ", placeOfInterest[i])
}
fmt.Printf("\n")
}

// plain string: ⌘
// quoted string: "\u2318"
// hex bytes: e2 8c 98
const nihongo = "日本語"
for index, runeValue := range nihongo {
fmt.Printf("%#U starts at byte position %d\n", runeValue, index)
}

// U+65E5 '日' starts at byte position 0
// U+672C '本' starts at byte position 3
// U+8A9E '語' starts at byte position 6

s = u"你好,中国"
print(len(s)) # 5
print(s[1]) # 打印'好'

s = "你好,中国"
print(len(s)) # 15
print(s[1]) # 打印的不是'好'
func main() {
s := "hello,中国"
fmt.Println(len(s))


r := []rune(s)
r[6] = '美'
fmt.Println(len(r))

e := string(r)
fmt.Println(e)
}
// 14
// 8
// hello,美国

关于Unicode,UTF-8和多语言文本处理,还有很多可以聊的。现在,我们希望您已经更好地了解Go字符串,尽管它们可能包含任意字节,但UTF-8是其设计的核心。

回答文章刚开始时提出的问题:字符串是由字节构建的,所以索引它们返回字节,而不是字符。字符串甚至可能不包含字符。事实上,“字符”的定义是不明确的,尝试通过定义字符串由字符组成来解决歧义是一个错误。

总结

对于上面的例子也可以看到,需要统计中文字符串长度时,也需要转换成对应的rune数组

因此必须先将字符串转换成字节数组(或者rune数组,对于中文等),然后再通过修改数组中的元素值来达到修改字符串的目的,最后将字节数组转换回字符串格式。

因为Go 语言中的字符串是不可变的,也就是说 str[index] 这样的表达式是不可以被放在等号左侧的。如果尝试运行 str[i] = ‘D’会得到错误:cannot assign to str[i]。

字符串的本质就是一个字节数组。在Go 语言里面字符串和字节数组可以相互进行显式转换,这一性质通常被用来“修改”字符串的内容。

同样我们知道string[index]获取的是字符byte,就无法像Python中通过加u前缀之后直接索引,在Go中需要将字符串转换成rune数组,runne数组中就可以通过数组下标获取一个汉字所标识的Unicode码,再将Unicode码按创建成字符串即可。

分析Python代码,我们可以看到,字符串前面加了u标识符,表示按照unicode方式索引,否则默认情况下按照索引得到的是字节索引(unicode下面中文用三个字节表示)。

编码过程中避免不了中文字符,那我们该如何提取一个中文呢? 在Python中,我们有:

中文字符相关

下面是一个使用%#U格式化的例子,它显示了代码点的Unicode值及其打印的表现形式。

而一个range循环会在每次迭代时,解码一个UTF-8编码的符文。每次循环时,循环的索引是当前文字的起始位置,以字节为单位,代码点是它的值。

除了Go源码是UTF-8外,Go只提供一种方法特殊处理UTF-8,那就是在字符串上使用for range循环。我们已经知道使用for循环会发生什么了。

range循环

  • Go源码总是UTF-8
  • 一个字符串包含任意个byte
  • 字符串常量如果缺少字节级转义,将始终保持UTF-8序列。
  • Unicode的代码点在Go语言中被称为rune
  • Go不保证字符串中的字符是规范化的。

总结一些前面的内容:

Go语言将rune定义为int32类型的别名,因此在使用一个整型值表达一个“代码点”时,代码更加清晰。此外,一个你可能认为是字符常数在Go中是符文常数。’⌘’的类型和值分别是rune和0x2318。

“代码点”这样的说法有点绕口,所以Go语言介绍了一个较短的术语概念:rune,符文。该术语出现字库和源代码中,和“代码点”表达的意思完全相同。还有一个有趣的补充。

因此,计算中的字符概念是模糊的,至少是混乱的,所以我们需要谨慎地使用它。有规范化的技术来保证字符和代码点的映射,不过这个领域和本文讨论的内容相去甚远。

举一个更普遍的例子,Unicode代码点U+0061表示小写拉丁字母’A’:a。但是小写的重音字母’A’: à怎么表示呢?这是一个字符,它可以用代码点U+00E0表示,但也有其它表示。例如,可以“组合”严重重音代码点U+0300,并将其附加到小写字母a,U+0061,以创建字符à。通常情况下,字符可以由多个不同的代码点序列表示,由此可以用不同的UTF-8字节序列表示。

我们一直非常小心地使用“字节”和“字符”这样说法。这部分是因为字符串中保存了字节,还有部分是因为“字符”的概念有点难以定义。Unicode标准使用术语“代码点”来用单个值表示一个字符。比如具有16进制值2318的代码点,U+2318表示符号⌘。

字节点,字符和rune

总而言之,字符串可以包含任意字节,但是当从字符串文字构造时,这些字节(几乎总是)是UTF-8。

有些人认为Go字符串总是UTF-8,但是不是这样:只有字符串字面量是UTF-8。正如上面所示,字符串值可以包含任意字节,只要没有字节级转义,字符串文字总是包含UTF-8文本。

简单来说,Go源码是UTF-8,因此字符串文字的源代码是UTF-8文本。如果该字符串文字不包含转义序列,构造的字符串将精确保存引号之间的源文本。因此,通过定义和构造,原始字符串将总是包含其内容的有效UTF-8表示。类似的,除非它包含类似上面例子中的UTF-8拆分转义,否则常规字符串字面值也将始终包含有效的UTF-8。

Go语言中的源代码定义为UTF-8文本,不允许其他的表示。也就是说,在代码中写下字符时,用于创建程序的文本编辑器将符号⌘的UTF-8编码放入源文本中。当打印16进制字节时,我们只是将文件中的数据打印出来。

上面的例子告诉我们,Unicode字符值U+2318,名胜古迹符号”⌘”的字节表示为”e2 8c 98”,这些字节是16进制值”2318”的UTF-8编码。

下面的程序用三种不同的方式打印一个字符串常量,一次作为纯字符串,一次作为只有ASCII的字符串,一次作为16进制的字节。为了避免混淆,创建一个“原始字符串”,用反括号括起来,因此它只包含文本。

正如我们看到的,索引一个字符串返回的是byte,而不是字符:一个字符串就是一堆字节。这意味着,当我们将字符存储在字符串中时,实际存储的是这个字符的字节。来看一个例子。

UTF-8和字符串

这些打印的小技巧在调试字符串内容的时候很有用,并且会方便下面的讨论。值得注意的是,上面的小技巧对于byte的切片一样适用。

如果不熟悉字符串中奇怪的字符,可以在打印的时候使用”+q”标识,这个标识采用UTF-8编码,它不仅会转义不可打印的字节序列,还会转义非ASCII码的字节。下面的代码将字符串中非ASCII数据对应的Unicode值打印出来。字符串中的瑞典字符作为Unicode字符,打印出来带有\u的转义符。

仔细观察,在一堆乱码中我们可以看到一个’=’号和一个空格符号,最后面是瑞典表示“名胜古迹”的符号,这个符号的Unicode值为U+2318,UTF-8编码为”e28c98”。

还有一些小技巧。使用q标识,可以将字符串中任何不可打印的字节序列转义。

还有一个打印的小技巧。

下面一种更简单的打印方式。

使用for循环遍历所有的字节。

要了解这个字符串究竟是什么,我们需要把它分开来检查一下。正如上面提到的,索引一个字符串,得到的是byte,而不是字符。

在上面的例子中,有一些byte并不是ASCII码,甚至也不是UTF-8编码,直接打印出来会出现乱码

打印字符串