Большой разбор Строк Go -> «Типы и структуры данных Go»

Доброе утро/день/вечер/ночь!

Меня зовут Рома и это вторая часть цикла «Типы и структуры данных Go». В этот раз будем разбираться с внутренностями строк. В первой части этого цикла я уже говорил, что какое-то время назад я захотел изучить всю внутрянку Go, заглянуть в исходники языка и понять, почему все устроено так, как устроено. В этот самый момент я обнаружил, что на просторах интернета практически отсутствуют материалы, которые подробно разбирают типы данных, их вспомогательные функции, детали реализации рантайма и так далее. Поэтому мной было принято решение сделать это самостоятельно. Изначально я занимался этим для себя, но позже решил, что стоит поделиться моими наблюдениями и выводами с миром.

Говорить будем только о том, что есть в базе языка, то есть без дополнительных функций из стандартной, экспериментальной или какой-либо другой библиотеки, так как рассмотреть настолько большой массив информации было бы слишком тяжело.

Приятного аппетита!

Строки

‎
Очень важно разделять представление в рантайме Go ИНФОРМАЦИИ/МЕТАДАННЫХ и ДАННЫХ типа, потому что это два разных уровня абстракции, каждый из которых играет свою роль в системе типов. Ниже поговорим о ИНФОРМАЦИИ/МЕТАДАННЫХ СТРОК.

ИНФОРМАЦИЯ/МЕТАДАННЫЕ — это цепочка описательных структур. Эта цепочка существует в одном экземпляре на тип. Она используется для того, чтобы понять сколько байт занимает значение типа, как копировать, сравнивать и очищать тип, какие поля или элементы тип содержит, где в памяти расположены указатели на тип (для сборщика мусора).

Изучим звенья этой цепочки по порядку.

→ rtype из go/src/runtime/type.go — структура, описывающая ИНФОРМАЦИЮ/МЕТАДАННЫЕ о любом типе Go в рантайме.

type rtype struct { *abi.Type } 

→ Type, встроенная в rtype структура, из go/src/internal/abi/type.go содержит поля для хранение ИНФОРМАЦИИ/МЕТАДАННЫХ о типе Go.

type Type struct { Size_       uintptr // Размер объекта данного типа в байтах PtrBytes    uintptr // Количество начальных байт, содержащих указатели (для сборщика мусора) Hash        uint32  // Хеш типа; используется для ускорения в хеш-таблицах TFlag       TFlag   // Дополнительные флаги информации о типе Align_      uint8   // Выравнивание переменной этого типа FieldAlign_ uint8   // Выравнивание поля в структуре с этим типом Kind_       Kind    // Вид типа (enum), совместим с C  // Функция сравнения объектов данного типа // принимает (указатель на объект A, указатель на объект B) → возвращает, равны ли они Equal func(unsafe.Pointer, unsafe.Pointer) bool  // GCData содержит данные для сборщика мусора. // Обычно это указатель на битовую маску, описывающую, // какие поля типа являются указателями (ptr) или нет (nonptr). // Маска содержит как минимум PtrBytes / ptrSize бит.  // Если установлен флаг TFlagGCMaskOnDemand, то GCData — это // **byte, и указатель на битмаску находится на один уровень разыменования глубже. // В этом случае рантайм сам построит маску при необходимости. // (см. runtime/type.go:getGCMask)  // Примечание: разные типы могут иметь одинаковое значение GCData, // включая случаи с TFlagGCMaskOnDemand. Такие типы, конечно же, // будут иметь одинаковое размещение указателей (но не обязательно одинаковый размер). GCData    *byte  Str       NameOff // Смещение к строковому представлению типа PtrToThis TypeOff // Смещение к типу указателя на данный тип, может быть нулём } 

→ Kind_ типа Kind внутри Type из go/src/internal/abi/type.go содержит uint8 (enum) обозначение типа Go.

→ Kind из go/src/internal/abi/type.go — кастомный тип, объединяющий константные обозначения типов Go.

type Kind uint8  const ( Invalid Kind = iota Bool Int Int8 Int16 Int32 Int64 Uint Uint8 Uint16 Uint32 Uint64 Uintptr Float32 Float64 Complex64 Complex128 Array Chan Func Interface Map Pointer Slice String Struct UnsafePointer ) 

Перейдем к представлению ДАННЫХ СТРОК в рантайме Go. Это будет маленький блок, потому что рассказывать особо не о чем.

ДАННЫЕ — это фактические данные типа, с которыми работает программа во время выполнения.

→ stringStruct из go/src/runtime/string.go — структура из двух полей, содержащая ДАННЫЕ СТРОКИ.

type stringStruct struct {     str unsafe.Pointer // Указатель на первый байт     len int            // Длина строки в байтах } 

Теперь, когда мы разобрались с представлениями строки в рантайме, пришло время поговорить о операциях связанных с этим типом и том, как они реализованы.

Сначала я буду давать небольшие выдержки из книги «The Go Programming Language» для общего понимания, как та или иная операция работает, а затем приводить подробный разбор внутренней реализации.

Доступ к байтам

fmt.Println(s[0:5]) // "hello" 

fmt.Println(s[:5])  // "hello" fmt.Println(s[7:])  // "world" fmt.Println(s[:])   // "hello, world" 

Извлечение подстроки (s[i:j]) — встроенная операция компилятора, реализованная без вызова функции. Память не копируется — создаётся новая “ссылка” на диапазон байт. Код проверяет границы, смещает указатель и задаёт новую длину.

Сравнение строк

Конкретная реализация может быть на Go или на ассемблере, в зависимости от архитектуры. Например, для arm64/x86 рассмотрена оптимизация через memequal или специальные ассемблерные расширения. В коде используется подход: cначала сравниваются длины строк, потом — их содержимое через memequal.

Конкатенация

fmt.Println("goodbye" + s[5:]) // "goodbye, world" 

Если конкатенируются строковые литералы, Go-компилятор сразу объединяет их на этапе компиляции. Если строк больше одной и они переменные, компилятор использует функцию рантайма concatstrings.

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 }  if l+n < l { throw("string concatenation too long") }  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 { n := copy(b, x) b = b[n:] }  return s } 

Преобразования

s := "abc" b := []byte(s) s2 := string(b) 

s := "abc" b := []byte(s) s2 := string(b) 

• Преобразование из string в []byte реализовано через функцию stringtoslicebyte (внутри go/src/runtime/string.go). stringtoslicebyte создаёт копию содержимого строки и возвращает срез []byte.

  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 в string реализовано через функцию slicebytetostring (внутри go/src/runtime/string.go). slicebytetostring создаёт новую строку, копируя байты из среза.

  // slicebytetostring преобразует срез байт в строку. // Эта функция вставляется компилятором в сгенерированный код.  // ptr — указатель на первый элемент среза; // n — длина среза. // buf — буфер фиксированного размера для результата, // он не равен nil, если результат не утекает из функции (escape analysis). func slicebytetostring(buf *tmpBuf, ptr *byte, n int) string { if n == 0 { // Это оказывается довольно частым случаем. // Например, когда вы хотите выделить данные между скобками в строке "foo()bar",   // вы находите индексы и преобразуете подстроку в строку. return "" }  // Поддержка race detector (детектора гонок). if raceenabled { racereadrangepc(unsafe.Pointer(ptr), uintptr(n), sys.GetCallerPC(), abi.FuncPCABIInternal(slicebytetostring)) }  // Поддержка MemorySanitizer. if msanenabled { msanread(unsafe.Pointer(ptr), uintptr(n)) }  // Поддержка AddressSanitizer. if asanenabled { asanread(unsafe.Pointer(ptr), uintptr(n)) }  if n == 1 { // Быстрая оптимизация для строк длины 1 — часто встречается. p := unsafe.Pointer(&staticuint64s[*ptr]) if goarch.BigEndian { // Смещение указателя в случае big-endian архитектуры. p = add(p, 7) } return unsafe.String((*byte)(p), 1) }  var p unsafe.Pointer  if buf != nil && n <= len(buf) { // Если доступен временный буфер, и он достаточно велик — используем его. p = unsafe.Pointer(buf) } else { // Иначе выделяем память в куче. p = mallocgc(uintptr(n), nil, false) } // Копируем байты в выделенную область. memmove(p, unsafe.Pointer(ptr), uintptr(n))  // Создаем строку из массива байт (без копирования). return unsafe.String((*byte)(p), n) } 

• Преобразование из string в []rune реализовано через функцию stringtoslicerune (внутри go/src/runtime/string.go). Происходит декодирование UTF-8 → int32. Создаётся новый []rune.

  func stringtoslicerune(buf *[tmpStringBufSize]rune, s string) []rune { n := 0  for range s { n++ }  var a []rune  if buf != nil && n <= len(buf) { *buf = [tmpStringBufSize]rune{} a = buf[:n] } else { a = rawruneslice(n) }  n = 0  for _, r := range s { a[n] = r n++ }  return a } 

• Преобразование из []rune в string реализовано через функцию slicerunetostring (внутри go/src/runtime/string.go). Кодирует каждую руну обратно в UTF-8, результат — строка.

  func slicerunetostring(buf *tmpBuf, a []rune) string { if raceenabled && len(a) > 0 { racereadrangepc(unsafe.Pointer(&a[0]), uintptr(len(a))*unsafe.Sizeof(a[0]), sys.GetCallerPC(), abi.FuncPCABIInternal(slicerunetostring), ) }  if msanenabled && len(a) > 0 { msanread(unsafe.Pointer(&a[0]), uintptr(len(a))*unsafe.Sizeof(a[0])) }  if asanenabled && len(a) > 0 { asanread(unsafe.Pointer(&a[0]), uintptr(len(a))*unsafe.Sizeof(a[0])) }  var dum [4]byte size1 := 0  for _, r := range a { size1 += encoderune(dum[:], r) }  s, b := rawstringtmp(buf, size1+3) size2 := 0  for _, r := range a { if size2 >= size1 { break } size2 += encoderune(b[size2:], r) }  return s[:size2] } 

Получение длины массива байт

s := "hello, world"      fmt.Println(len(s))    // "12" 

В Go встроенная функция len() для строки реализована не как обычная функция, а как компиляторная операция: компилятор напрямую обращается к полю длины строки — без вызова отдельной функции.