mirror of
https://github.com/Nekrolm/ubbook.git
synced 2025-12-17 21:04:35 +03:00
140 lines
9.9 KiB
Markdown
140 lines
9.9 KiB
Markdown
# NULL-терминированные строки
|
||
|
||
В начале 70-х Кен Томпсон, Деннис Ритчи и Брайан Керниган, работая над первыми версиями C и Unix, приняли решение, которое отзывается болью, страданиями, багами и неэффективностью до сих пор, спустя 50 лет.
|
||
Они решили, строки, как данные переменной длины, нужно представлять в виде последовательности, заканчивающейся терминирующим символом -- нулем. Так делали в ассемблере, а C ведь высокоуровневый ассемблер! Да и памяти у старенького PDP не много: лучше всего один байтик лишний на строку, чем 2, 4, а то и все 8 байтов для хранения размера в зависимости от платформы... Не, лучше байтик в конце!
|
||
Но в других языках почему-то предпочли хранить размер и ссылку/указатель на данные...
|
||
|
||
Ну что ж, посмотрим, к чему это привело
|
||
|
||
### Длина строки
|
||
|
||
Единственный способ узнать длину NULL-термирированной строки -- пройтись по ней и посчитать символы. Это требует линейного времени от длины строки.
|
||
|
||
```C++
|
||
const char* str = ...;
|
||
for (size_t i = 0 ; i < strlen(str); ++i) {
|
||
...
|
||
}
|
||
```
|
||
|
||
И вот уже этот простенький цикл требует не линейного числа операций, а квадратичного. Это известный пример. Про него даже известно, что умный компилятор способен вынести вычисление длины строки из цикла
|
||
|
||
```C++
|
||
const char* str = ...;
|
||
const size_t len = strlen(str);
|
||
for (size_t i =0 ; i < len; ++i) {
|
||
...
|
||
}
|
||
```
|
||
|
||
Но ведь пример может быть и посложнее. В коде одной там популярной игры про деньги, разборки мафии и угон автомобилей обнаружили занятный пример парсинга большого массива чисел из json-строки с помощью `sscanf`
|
||
|
||
Выглядел он примерно (его получили путем реверс-инженеринга конечного бинарного файла) так
|
||
|
||
```C++
|
||
const char* config = ...;
|
||
size_t N = ...;
|
||
|
||
for (size_t i =0 ; i < N; ++i) {
|
||
int value = 0;
|
||
size_t parsed = sscanf(config, "%d", &value);
|
||
if parsed > 0 {
|
||
config += parsed;
|
||
}
|
||
}
|
||
```
|
||
|
||
Прекрасный и замечательный цикл! Тело его выполняется всего `N` раз, но на большинстве версий стандартной библиотеки C каждый раз требует `strlen(config)` операций на интерацию. Ведь `sscanf` должен посчитать длину строки, чтоб случайно не выйти за ее пределы! А строка NULL-терминированная.
|
||
|
||
Вычисление длины строки -- невероятно часто всречающаяся операция. И один из самых первых кандидатов на оптимизацию -- посчитать ее один раз и хранить со строкою... Но зачем тогда NULL-терминатор? Только лишний байт в памяти!
|
||
|
||
|
||
### С++ и std::string
|
||
|
||
C++ высокоуровневый язык! Уж повыше C, конечно. Стандартные строки в нем уже, учтя ошибку C, хранятся как размер + указатель на данные. Ура!
|
||
|
||
Но не совсем ура. Ведь огромное число C библиотек никуда не денется, и у большинства из них в интерфейсах используются NULL-терминированные строки.
|
||
Поэтому `std::string` тоже обязательно NULL-терминированные. Поздравляю, мы храним один лишний байт ради совместимости. А еще мы его храним неявно: `std::string::capacity()` на самом деле всегда на 1 меньше действительно выделенного блока памяти.
|
||
|
||
### C++ и std::string_view
|
||
|
||
"Используйте `std::string_view` в своих API и вам не придется писать перегрузки для `const char*` и `const std::string&` чтобы избежать лишнего копирования!"
|
||
|
||
Ага, конечно.
|
||
|
||
`std::string_view` это тоже указатель + длина строки. Но уже, в отличие от `std::string`, указатель не обязательно на NULL-терминированную строку (Ура, мы можем использовать `std::vector` и не хранить лишний байт!).
|
||
|
||
Но если вдруг за фасадом вашего удобного API со `string_view` скрывается обращение к какой-нибудь сишной библиотеке, требующей NULL-терминированную строку...
|
||
|
||
```C++
|
||
// Эта маленькая программа весело и задорно выведет
|
||
|
||
// Hello
|
||
// Hello World
|
||
|
||
// Хотите вы этого или нет.
|
||
|
||
void print_me(std::string_view s) {
|
||
printf("%s\n", s.data());
|
||
}
|
||
|
||
int main() {
|
||
std::string_view hello = "Hello World";
|
||
std::string_view sub = hello.substr(0, 5);
|
||
std::cout << sub << "\n";
|
||
print_me(sub);
|
||
}
|
||
```
|
||
|
||
Чуть-чуть [изменим](https://godbolt.org/z/qPoeha4jc) аргументы
|
||
|
||
```C++
|
||
// Теперь эта маленькая программа весело и задорно выведет
|
||
|
||
// Hello
|
||
// Hello Worldnext (а может быть просто упадет с ошибкой сегментации)
|
||
|
||
// Хотите вы этого или нет.
|
||
|
||
|
||
void print_me(std::string_view s) {
|
||
printf("%s\n", s.data());
|
||
}
|
||
|
||
int main() {
|
||
char next[] = {'n','e','x','t'};
|
||
char hello[] = {'H','e','l','l','o', ' ', 'W','o','r','l','d'};
|
||
std::string_view sub(hello, 5);
|
||
std::cout << sub << "\n";
|
||
print_me(sub);
|
||
}
|
||
```
|
||
|
||
|
||
Функция не менялась, мы просто передали другие параметры и всё совсем сломалось! А это всего лишь `print`. С какой-то другой функцией может случиться что-то совершенно немыслимое, когда она пойдет за границы диапазона, заданного в `string_view`.
|
||
|
||
Что же делать?!
|
||
|
||
Нужно гарантировать NULL-терминированность. А для этого надо скопировать строку... Но ведь `std::string_view` мы же специально использовали в API, чтобы не копировать?!
|
||
|
||
Увы. Как только вы сталкиваетесь со старыми C API, оборачивая их, вы либо вынуждены писать две имплементации -- с сырым `char*` и c `const std::string&`. Либо соглашаться на копирование на каком-то из уровней.
|
||
|
||
### Как бороться
|
||
|
||
Никак.
|
||
|
||
NULL-терминированные строки -- унаследованная неэффективность и возможность для ошибок, от которых мы уже, вероятно, никогда не избавимся. В наших силах лишь постараться не продолжать плодить зло:
|
||
В новых C-библиотеках стараться проектировать API, использующие пару указатель + длина, а не только лишь указатель на NULL-терминированную последовательность.
|
||
|
||
От этого наследия страдают программы на всех языках, вынужденные взаимодействовать с C API.
|
||
Rust, например, использует отдельные типы `CStr` и `CString` для подобных строк и переход к ним из нормального кода всегда сопровождается мучительными тяжелыми преобразованиями.
|
||
|
||
Использование NULL-терминатора встречается не только для текстовых строк. Так, например, библиотека [SRILM](http://www.speech.sri.com/projects/srilm/) активно использует 0-терминированные последовательности числовых идентификаторов, создавая этим дополнительные проблемы.
|
||
Семейство функций exec в Linux принимают NULL-терминированные последовательности указателей.
|
||
EGL использует для инициализации списки атрибутов, оканчивающиеся нулем.
|
||
И многие многие другие.
|
||
|
||
Не нужно дизайнить неудобные, уязвимые к ошибкам, API без великой надобности. Экономия в функции на одном параметре, размером в указатель, редко когда оправдана.
|
||
|
||
|