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

Меня зовут Рома и это вторая часть цикла «Типы и структуры данных 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() для строки реализована не как обычная функция, а как компиляторная операция: компилятор напрямую обращается к полю длины строки — без вызова отдельной функции.