Безразличие к регистру — ошибка на миллиарды долларов

К данной статье я намеренно переиначил популярный в некоторых кругах заголовок («Billion dollar mistake» про null как значение ссылок/указателей). См. в конце статьи замечание про исходный случай. Но, в отличие от него, безразличие к регистру действительно является диверсией.

(О чём вообще речь?)

Для русского традиционными терминами являются «заглавная буква» и «строчная буква». Для английского было бы соответственно capital и line letter, но из типографской практики пришли и закрепились характеристики upper case и lower case, соответственно, верхний и нижний регистр букв. (Иногда строчные буквы путают с прописными. В строгих правилах это таки разное: прописные это графический формат для ручного написания.)

Во всей последующей статье будем использовать (относительно стандартные) сокращения:

• CI — case insensitive — безразлично к регистру (AA, Aa, aA, aa — одно и то же).

• CS — case sensitive — регистр важен (AA, Aa, aA, aa — 4 разных значения).

Древние письменности регистра букв не знали. Его появление — тема отдельного рассмотрения; античность и раннее средневековье знали неустойчиво и только в части стилей, но к началу использования не-типографских технических средств для передачи текста (светотелеграф, затем азбука Морзе) — разделение букв устоялось в основных европейских письменностях.

Светотелеграф и электрический телеграф фактически начали заново, с чего начинали древнейшие письменности: отсутствовали пробелы, регистр букв, сильно ограничена пунктуация. (ШАРИКСМАТРОСКИНЫМНАЧИНАЮТРАЗДЕЛИМУЩЕСТВАТЧК) Первые компьютерные кодировки следовали этому (ну, пробел добавили, точки и запятые). Но первые стандарты — ASCII (IA5 в интернациональном варианте) и EBCDIC уже имели это различие, даже если оно минимально использовалось.

В программах для компиляторов S/360 середины 1960-х понимались только заглавные буквы. В именах файлов допускались только заглавные буквы. Введение строчных в языки программирования это в массе уже 1970-е.

У нас есть два основных места, где проблемы лезут до невыносимости: файловые системы (видно в основном конечным пользователям) и сетевые протоколы (видно в основном программистам). Есть немного в языках программирования и вокруг (как Fortran, SQL, HTML). Ограничимся пока двумя, хотя базисты-DBA наверняка расскажут много ещё интересного.

(И таки шо мы имеем с гусь?)

В файловых системах

Самый известный пример безразличия к регистру — файловые системы ОС Windows. Как оно появилось?

Операционные системы PDP-11, такие, как RSX-11 и RT-11, имели следующую файловую систему: имя файла представляло собой 4 символов из набора RADIX-50. 50 в восьмеричной означало 40 возможных символов, из которых 26 были буквами английского алфавита. Регистр у этих букв не существовал. Обычные утилиты выводили заглавными буквами, но принимали в обоих регистрах.

Для технического уровня PDP-11 это было вполне нормально (а для советских адаптаций с KOI-7 даже полезно, привет, IНЖАЛИД DЕЖИЦЕ). Но что получилось дальше?

CP/M была сделана на основе идей RSX-11, с переносом на процессоры типа 8080. Далее MS-DOS была сделана максимально похожей на CP/M. По всей цепочке была сохранена регистронезависимость, при том, что от RADIX-50 перешли к прямому хранению байтов, а все кодировки были основаны на ASCII, то есть уже с обоими регистрами «из коробки».

Устранив RADIX-50 и введя передачу имён файлов в побайтовой кодировке (для имён формата 8+3, типа GOODWYNN.WIZ, занималось 11 байт), были сохранены принципиальные ограничения на набор символов в именах (хоть и заметно более широкие)… безразличие к регистру не было устранено, и имя всегда сохранялось заглавными.

Начиная с Windows 95 было введено сохранение регистра имени и CI сравнение. При этом Goodwynn.txt, GOODwynn.TXT — одинаковые имена для поиска, но разные для показа (хотя, если все заглавные, показ в проводнике переводил в форму — одна первая заглавная). Это то, что имеем сейчас.

Что по крайней мере странно в этом подходе? Почему файловые системы Windows различают «foo.docx», «foo. docx», «foо.docx», «foο.docx» и «fo​o.docx» (кто увидит разницу?), но не различают «foo.docx» и «Foo.docx»?

Где логика, Карл?

В Unix всегда было проще, но за счёт того, что этот вопрос вообще не поднимался. Везде, где не возникало внешнего воздействия в виде требования к CI, оставались не просто CS, но побайтовое равенство. Согласен, так проще. Но с какого-то момента (массовая юникодизация) этого стало не хватать.

(Отдельные интересные эффекты тут возникают при присутствии одновременно, например, Makefile и makefile. Или в одном проекте у нас был proxy.cxx — с main(), а Proxy.cxx — с главным классом. Попытка работы с ним на маке при настройках FS по умолчанию давала интересные искры.)

Сетевые протоколы

Из всех протоколов для нас важнейшим является HTTP. (П.С.С. Леонида Ильича Уварова-Мунина, том 80, стр. 404.) Пример с HTTP, версии 1.1, согласно RFC2616.

Все названия полей заголовка (или, на стандартном жаргоне, просто заголовков) регистронезависимы, можно сформировать в виде

CONTENT-TYPE: TEXT/HTML

или

Content-Type: text/html

(так делают почти все)

или

content-type: text/html

или

CoNtEnT-tYpE: tExT/hTmL

(законно!)

Не вспоминаем ещё, что можно писать и в виде

Content-TYPE                    :                                        TexT  /                       HtmL

(строка, начинающаяся с пробела или табуляции, продолжает поле заголовка, начатое в предыдущих строках) — это отдельная тема.

Что из этого реально используется? Практически все формируют названия полей заголовка в каноническом виде — каждое слово со своей заглавной, без пробела перед ‘:’, с одним пробелом после ‘:’. Остальные параметры пишутся всеми строчными, типа text/html;q=0.9. Но воспринимать на чтение участники обязаны все варианты, какими бы странными они ни казались.

Представим себе, что протокол был бы в виде:

ct=text/html cl=534

(без пробелов, без табуляций) — кому было бы хуже от этого?

С HTTP я больше, чем минимальные клиенты и серверы, не возился (думаю, авторы всяких браузеров и серверов могут тут рассказать много интересного), но постоянно приходится иметь дело с SIP, синтаксис которого очень близок по подходам и деталям. О нём чуть дальше, а пока что посмотрим на интересный пассаж из RFC2616:

When comparing two URIs to decide if they match or not, a client SHOULD use a case-sensitive octet-by-octet comparison of the entire URIs, with these exceptions:

• A port that is empty or not given is equivalent to the default port for that URI-reference;

• Comparisons of host names MUST be case-insensitive;

• Comparisons of scheme names MUST be case-insensitive;

Но что мы можем прочитать про схему? Тоже интересно (RFC1738):

Scheme names consist of a sequence of characters. The lower case letters «a»—«z», digits, and the characters plus («+»), period («.»), and hyphen («-«) are allowed. For resiliency, programs interpreting URLs should treat upper case letters as equivalent to lower case in scheme names (e.g., allow «HTTP» as well as «http»).

То есть генерировать надо строчными. Но воспринимать рекомендуется (в этой редакции слово should ещё не выделено заглавными, но мы-то знаем, что это значит «только если у вас нет уважительных причин не делать это»). Будем искать уважительные причины? Наверно, придётся, чтобы было побольше интересных эффектов в плане секьюрити.

Кажется, кто-то принял максиму Постела «be liberal in what you get» как разрешение вседозволенности и безнаказанности.

Некоторые сайты выполняют CI разбор URL всегда. Сюда входит, например, stackoverflow.com и вся группа stackexchange. (Связано ли это с ASP.NET движком и, соответственно, традициями Windows?) Reddit безразлично воспринимает регистр имени субреддита, но начальные /u/, /r/ в URL ему важны строчными. Подробнее я не копал, достаточно принципиального факта таких различий в подходах.

Приблизимся к SIP. Тут ещё больше интересных разнообразных проблем. (Больше я про него рассказывал тут. Осторожно, на ночь не читать.)

​1. Call-id является CS (RFC3261 строка 2086).

​2. Теги диалогов являются CI (строка 1750, потому что они tokens).

2ʹ. Часть реальных SIP агентов требует сохранения того же регистра букв в тегах,
что они послали, потому что теги у них реализованы как CS. Вынуждены подчиниться и ввести сохранение в исходном виде.

2ʺ. Часть реальных SIP агентов переводит теги всегда к некоему каноническому виду (например, заглавными) — если мы послали AbC, то они нам ответят ABC. Значит, сравнивать надо всегда в CI режиме. Удобно также при этом хранить канонизированную форму для внутреннего индексирования.

​3. Полный идентификатор диалога, состоящий из call-id и 1 или 2 тегов, является одновременно CI и CS. Ну хм, допустим… (мы уже видели похожее с URL в общем: схема и хост CI, остальное CS)

И как это выглядит в примере:

To: Bob <«sip»:«bob»@biloxi.com>;tag=a6c85cf From: Alice <«sip»:«alice»@atlanta.com>;tag=1928301774 Call-ID: «a84b4c76e66710@pc33.atlanta.com» 

Так как красить код в кодовом блоке нельзя, я CS части пометил «ёлочками» (в реальном тексте их, конечно, нет). Остальное — CI. Логично, да? (Кстати!: call-id может содержать после ‘@’ то, что обычно выглядит как привычный домен DNS, который вроде бы везде CI. Реально же это CS «word», и значения «moo@example.com» и «moo@Example.com» это разные call-id. Это ещё больше, чтобы вы не расслаблялись.)

Думаете, это всё?

The SIP-Version string is case-insensitive, but implementations MUST send upper-case.

Ну и из практики — очередное чудо, с которым таки требуется интероперабельность, хочет, что если оно написало в URL «transport=UDP», мы не можем прислать ему в ответе «transport=udp».

Правила сравнения SIP/SIPS URI предполагают, аналогично, безразличие к регистру почти везде, кроме userinfo. (Там хуже — ещё и требуется, чтобы состав параметров сравнивался независимо от их порядка задания в URI. Но так как каждый второй это игнорирует, параметры должны возвращаться в том же порядке, как они поступили от другого участника.)

Даже если ограничиться парсингом слов…

Сначала ограничимся ASCII. Ну так, для простоты. Чем это хорошо — набор символов мал, фиксирован, правила сравнения просты. Для большей части кода достаточно strncasecmp(), если мы рассматриваем именно по строкам. С другой стороны, эта функция уже внутри себя сравнивает символы, конвертируя обе стороны к (неважно, заглавным или строчным) одинаково — лишняя работа. Можно ли её упрощать и ускорять? Можно, но громоздко. Обратимся к коду одной из самых быстрых реализаций — Kamailio, в девичестве Sip Express Router. Ограничусь одним примером, а то и так по древу бегает стая мысей.

/*! \brief macros from parse_hname2.c */ // Оптимизировано для little-endian. -- netch80 #define READ(val) \ (*(val + 0) + (*(val + 1) << 8) + (*(val + 2) << 16) + (*(val + 3) << 24))  #define LOWER_DWORD(d) ((d) | 0x20202020)  ...  #define _cont_ 0x746e6f63 ...  ...                                 // например возьмём этот кусок. -- Netch                                 if ((LOWER_DWORD(READ(c)) == _cont_) &&                                         (LOWER_DWORD(READ(c+4)) == _ent__) &&                                         (LOWER_DWORD(READ(c+8)) == _type_)                                 ) {                                         /* Content-Type HF found */

Если непонятно — тут у последовательности из 4 символов сбрасывается регистр в нижний (через OR с 0x20), причём если это была не буква, то коду всё равно — дальше он будет сравнивать с буквами. Результат сравнивается с набором последовательностей из 4 букв в виде 32-битного слова. Апплодирую хакерскому стилю, Уоррен точно бы порадовался.

Ну, это хорошо работает на C. (Clang умудрился свернуть READ в просто 32-битное чтение из памяти. GCC этого не сумел. Ну не так страшно. И ещё нужна платформа с разрешением невыровненных чтений.) Уже на Java надо финтить, но хотя бы есть ByteBuffer. На интерпретаторах вроде Python, и на Java на строках, это превращается в чудовищную затрату или времени, или памяти, или обоих сразу.

На ASCII примера достаточно, чтобы показать и простой подход, и ускоренный. Но дальше у нас есть другие кодировки, вплоть до юникода во всех видах. Если нужно его учитывать, то происходит чудовищное удорожание процесса и, главное, его нестабильность! Про это ниже («турецкий тест»).

HTTP везде вокруг нас, и заметная часть до сих пор 1.1. Есть ещё email, с тем же синтаксисом в принципе. Есть близкие протоколы типа SMTP, POP3, IMAP, NNTP. Есть много других средств. Если подсчитать, сколько весь мир теряет на этих преобразованиях и сравнениях там, где им делать нечего… думаю, миллиардом в год не ограничимся.

Насколько важен регистр букв?

Очевидно, что самому компьютеру пофиг: он смотрит на байты, и чем ближе сравнение к сравнению двух цепочек байт на полное равенство, тем ему проще. Проблемы надо оценивать с точки зрения человека.

Типовым аргументом в пользу сохранения безразличия к регистру является так называемая «человекочитаемость«. Что в ней не так?

А «не так» то, что её путают с человекоозвучиваемостью. Читать глазами мы можем видя регистр без проблем (кроме случаев букв типа Оо одиночных вне рамок текста, но это я бы не считал проблемой). А вот в голосовой передаче регистра нет, если явно не выделять интонацией (очень искусственно) или обозначать отдельными словами (занудно).

В каких случаях могут быть проблемы с человекоозвучиваемостью?

Один из очевидных примеров — имена и фамилии. Но, очевидно-2, это особый контекст. У него есть свои проблемы. McLeod и Macleod это один человек или два? Имена Jane и Jayne (герой сериала «Firefly») это одно и то же имя? Кто помнит, что Джейн Эйр была Eyre, а не Air, Aire, или Heir? Олейников и Алейников — как передать, что это разные фамилии? Только ли в регистре дело?

Если вы видите букву H, это «эйч» («аш») латинское, «эн» кириллическое или «эта» («ита») греческое? Как её читать, если язык не понятен, и чем бы нам помог регистр?

Если есть те, кому в конкретном варианте важна человеко-озвучиваемость строк, то ограничений должно быть в разы больше, чем просто несовместимость вариантов, отличающихся только регистром. Почему в NTFS допустимо «Any Unicode except NUL, \, /, :, *, «, <, >, |»? Почему допустимы какие-нибудь no-break space (в нескольких вариантах), right-to-left override (привет, поддельный показ имён), одновременно допустимы ‘, ʼ, ’ и ′; A, А и Α? Если ставится вопрос об озвучиваемости, то ничего кроме букв и цифр не должно допускаться (и мы возвращаемся к RADIX-50, где таких проблем не было).

Да, сравнение — должно иметь контексты, в которых регистр не различается. Но в таких контекстах вообще нужен (человеку! не компьютеру) неточный поиск с оценкой степени совпадения. Такой, чтобы нашёл не только с разницей в регистре, но и с опечаткой, пробелами (Lavey или La Vey? а как насчёт von Neumann?), в вариантах написания (по «McLeod» чтобы нашёл «Маклауд») и даже если xfcnm ntrcnf yf,hfyf d lheujq ht;bvt ddjlf. А просто выставить букву уже не должно быть проблемой.

Эффекты контекста

Вообще, ситуации, когда регистр не имел бы значение, можно представить себе и без легаси. Но при этом надо реализовывать эту задачу грамотно. Вспоминаем Turkey test:
* в не-турецкой локали (культуре, в терминах дотнета): I<->i.
* в турецкой локали: I<->ı, İ<->i.

Очевидный тест: создаём два файла: I1 и ı1 при, например, американской локали. Они, безусловно, раздельны. Переключаемся в турецкую. При поиске по I1, который из файлов будет найден, и почему? Мы заранее не знаем (порядок записей в каталоге? ı1 может оказаться первым — например, если какой-то файл был удалён между двумя созданиями). А как нам открыть другой?

Пока что имеем странные эффекты типа такого (орфография сохранена):

А у винды есть таблица преобразований для того что бы большие и маленькие буквы не отличались и как прнято в Микрософт в разных местах эта таблица может отличаться. В консоли файл создаётся, а explorer — переименовать файл не может, то кавычки не такие и файл не найжде, то пробелы в начале или конце файла и амба.

Из этого вытекает ещё одно соображение: если есть хотя бы потенциальная возможность попасть в такую ситуацию, должна быть опция поиска по имени с запретом всех преобразований. (Не обязательно создания — создание может быть и запрещено в таком режиме, или требовать спец-опцию — а поиска уже существующего, открытия его по такому имени, переименование в другое имя. Для целевого переименования уже можно применять ограничения. Для бэкапных назначений, понятно, их не должно быть.)

И это тоже для случая юникода: являются ли U+00CF (Ï), U+0049 U+0308 (Ï), U+03AA (Ϊ), U+0399 U+0308 (Ϊ), U+0407 (Ї), U+0406 U+0308 (Ї), одним и тем же именем? Почему бы нет? А если да?

По-нормальному это всё надо решать установкой политики на уровне каталога (даже не файловой системы). CI или CS, какая локаль, ограничиваем ли набор символов конкретной письменностью (только латиница, только кириллица) или группой, применяются ли правила нормализации юникода. Может, даже уплощение с исключением пробелов, запретом пунктуации… Сейчас это так (хотя бы частично) работает в нормальных СУБД, правила выставляются для таблицы или колонки таблицы, типа такого или такого. И, опять же, никакой насильной регистронезависимости, и расчёта на неё в системных средствах.

Тренды-тенденции. Камо грядеши, так сказать.

Что мы имеем с этот гусь сейчас, кроме бло́хи?

Старое цепляется за своё зубами и когтями. Новое приходит в новые ниши и уже не имеет этих проблем. Основная реформа уже состоялась за счёт новых технических средств — JavaScript, JSON, YAML… у всех сравнение ключей — CS, значения воспринимаются CS. Но плавная замена происходит описанным у Еськова методом: первыми захватывают (и создают) новые территории, остальным приходится подлаживаться под них; старые же сохраняют свою… мнэээ… специфику, и мы имеем хвойные леса и заросли из хвощей.

С другой стороны, в этих новых средствах различают и то, что не должно было бы различаться с точки зрения человека(?) Те же Á (00C1) и Á (0041 0301) — что в Python, что в Javascript разные ключи. JSON не имеет требования нормализации ключей по какой-нибудь NFC. А вот такие же переменные Á и Á в Python идентичны, это документировано правилами парсинга кода с нормализацией. Можно ожидать странных эффектов. Считать это недоработкой, или нет? Но они в этом смысле хотя бы не хуже того безобразия, что было с CI.

Самой дикостью выглядит подход типа того, как у Microsoft в PowerShell, где даже строки данных по умолчанию являются CI (ещё можно было бы понять для команд, но для данных???) Впрочем, судя по такому, уже и в Microsoft начали сдвигаться. Только медленно…

Просьба к тем, кто создаёт новое: не повторяйте этой ошибки. Сначала подумайте, что именно вам нужно не учитывать, и как именно. Только после этого можно вводить правила. И я не только о регистре. К сожалению, тотально всё загнать в какой-нибудь ElasticSearch пока слишком дорого. Но надо думать в эту сторону в принципе.

Вдогонку

К заголовку данной статьи. Сразу заявлю: я не согласен с Хоаром нынешним и согласен с Хоаром 1960-х. Самокритика в общем — прекрасно, но тут она совершенно неуместна. На момент введения такого null альтернативы ему не было, не хватало мощности компьютеров. Только последние лет 10 мы получили в доступной активной практике такие типы, как Optional[X] или Nullable[X], раньше же это было неподъёмно для компиляторов. Но это точно не вопрос для данной статьи.

Сверх-грамматизация (причём в странных манерах) в разработках IETF до 2000-2005 (на глаз) — все старые протоколы их разработки уровней L5-L7 (по OSI) страдают этим. После этого жизнь немного придавила (HTTP/2, HTTP/3, JSON), но слишком много хвостов остаётся в активном применении. Эта проблема, которая требует отдельного рассмотрения.