Как лучше хранить строки в интерпретаторе языка?

собственно сабж... делаю свой интерпретатор (виртуальную машину) для байткода своего языка программирования... он должен одинакого собираться и работать под все винды начиная с 2000 и под большинство десктопных линуксов... относительно строк думал делать, как в Питоне, то есть в байткоде и в виртуальной памяти строки хранятся в кодировке UTF-8... но пока не понятно, как в таком случае производить обработку строк, ведь в UTF-8 символы не одинакового размера (от 1 до 4 байт). придется видимо копаться в исходниках какого-нить iconv'а и писать собственные функции основываясь на нем... и, так как мой язык должен уметь вызывать апи-функции операционной системы, наверняка возникнут ситуации, в которых необходимо будет переводить строку из UTF-8 в текущую локаль (видимо в винде MultyByteToWideChar, а линуксах придется пользоваться iconv'ом)... какие у вас есть мысли по этому поводу? может быть я выбрал неверный путь? я раньше мало сталкивался с проблемами кодировок и подобным...

 

Rel

А в чём проблема? strcmp работает и на utf8 не хуже, чем на однобайтовой кодировке. strlen тоже работает, правда, возвращает длину не в символах, но в байтах. Но несложно написать свою "strlen", которая будет считать символы, несложно выяснить размер utf8 символа по первому его байту.
Или проблема с написанием функции типа getc? Ну дык getc возвращает int, а в int вполне влезает любой символ UTF8. Или тебе просто необходим random access к символам строки по номеру символа? Если так, то стоит посмотреть в сторону wchar_t.

В линуксах в качестве текущей локали используется ru_RU.UTF8. По-крайней мере в подавляющем большинстве десктопных линуксов. Динозавров, которые предпочитают однобайтовые кодировки типа koi8-r уже практически не осталось. Даже я, несколько лет тому назад взгеморроился и перекодировал всё на жёстком диске из koi8-r в utf8, и перешёл на utf8.
В венде, насколько я знаю, используется utf16. Из utf8 в utf16 перевести и обратно -- это не проблема. Тем более что есть, как ты говоришь, MultiByteToWideChar.

Всё очень просто. Раздели у себя в голове понятия "внешняя кодировка" и "внутренняя кодировка". Внешняя -- это кодировка в которой выполняется общение с внешними API, внутренняя -- это та, которую использует программа. Внутренняя она ровно одна, её выбор производится ещё до начала написания программы. Единственное обязательное требование к внутренней кодировке: она должна быть в состоянии закодировать все символы, которые могут встретится. Внешних же кодировок может быть тьма. Напиши обёртки над всеми используемыми библиотеками, которые принимают в качестве аргументов строки или возвращают строки. И прозрачно всё перекодируй в этих обёртках. После чего забудь про кодировки насовсем.

И что? API-функции они же все в latin1. В обёртке пробегаешься по строковому аргументу, убеждаешься что в нём нет байт со значением >127, и передаёшь в win32api. Правда может быть ещё перекодировать придётся -- тут не скажу, с win32api не знаком.

 

Rel
Видел одну реализацию, которая пришлась мне по душе. Строки хранятся в UTF-8, при загрузке они помещаются в определённую структуру и конвертируются в wide.
struct UTF8String {
uint8_t *utf8_string;
wchar_t *wide_string;
};
Работа по модификации строки проводится только над utf16_string (при каждой модификации необходимо занулять utf_8string). Если, вдруг, понадобится строка в кодировке UTF-8 (например, при сохранении в файл), проверяется, равен ли указатель utf8_string NULL, и, если да, происходит конвертация wide string в UTF-8 string.

 

r90
Проблем на самом деле много, просто они не очевидны. Представьте, что Вам нужно найти определённый символ, начиная с конца строки.

А вот это - дело.

 

А чего тут думать? UTF-16 и строка со счётчиком в начале. Причём на самый факт существования диапазона 10000h-... можно плюнуть и забить. Строки без счётчика по нынешнем временам вообще дерьмо дремучее, ещё при динозаврах протухшее и с какой-никакой производительностью при большинстве строковых операций (особенно при вычислении длины) абсолютно несовместимое.

 

CyberManiac

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

 

r90
Всё очень просто, он поклонник Delphi ;D

 

Ezrah

А дельфи-то здесь причём? Да собственно дельфи здесь без разницы. Какое отношение имеют его поклонения к кодировкам?

 

Опять сейчас флуд начнётся. Я не буду отвечать.

 

да... это одна из проблем UTF-8... просто не хочется чтобы достать один символ сканить всю строку с начала... а насчет wchar_t - то он не является кроссплатформенным типом... в винде наверное 2 байта, на моей оупенсусе 4 байта, как контейнер для какой-нить кодировки фиксированной длины он сгодиться, но отводить 4 байта на символ... это как-то не экономно... UTF-8 мне как раз таки и нравится своей экономичностью, тем более что наиболее вероятно будут использоваться Latin-1 в основном...

вообще можно конвертировать в какую-нить 16-битную кодировку фиксированного размера символа (символ в UTF-16 может занимать и 4 байта)... но надо подумать в какую, и что делать с символами которые не влезают в эти 65536 ячеек...

да в винде UTF-16... но не понятно, что они делают с диапазоном 0x10000 - 0x10FFFF... вообще в винде можно использовать эти символы так для имен файлов, или веток реестра?

да это-то понятно... я вот и думаю сейчас о выборе "внутренней кодировки"... мне нравится UTF-8, кроме некоторых сложностей в алгоритмах по работе со строкой, как с массивом символов (аналогов strchr, strrchr, strstr, strtok и тд), так как в любом случае придется проходить строку с начала вне зависимости от алгоритма... надо будет покопаться в исходниках Питона, посмотреть как там эти моменты реализованы...

 

Rel
Есть правило обработку надо вести в том формате в котором её удобнее вести. А вот ввод и вывод это отдельное преобразование. Обработку удобнее вести в 4 байтном коде. Если много то можно обрезать, до 2байтовой, выкинув лишние символы.

 

Rel

Проще, конечно, выбросить Но есть UTF-32, если мегабайт не жалко.

Угу. Когда цифра обычно весит один байт, а буква - два, это так удобно программировать... И работает на удивление быстро... И позиция символа в памяти легко вычисляется... И размер буфера под строку такой предсказуемый... UTF-8 придумали, чтобы с перекодировкой текста на латинице не сильно трахаться. Сляпали по-быстрому из того, что было, но по факту - крайне неудачный стандарт.

 

какой же из "стандартов" удачен в вашем понимании? и почему?

 

Rel

Зачем копаться. Алгоритм и так виден. Берём младший байт искомого символа и ищем его. Когда найдём, разруливаем мультибайтность вовсю пользуясь тем моментом, что код однобайтного символа никогда не совпадёт с кодом ни одного байта многобайтного. Быть может выяснится, что мы нашли не тот байт -- но это вряд ли, это случится только тогда когда ищем многобайтовый символ, и имеем дело со строками в которых символы как минимум из двух двухбайтовых "алфавитов". Но если всё же такое случится, то поиск несложно перезапустить. Скажем, набросок strrchr:

Код (Text):

1. char *my_strrnchr(const unsigned char *s, int c, int len)
2. {
3.         char *p = memrchr(s, c, len);
4.         if(c <= 0x7f)
5.             return p;
6.         else if(c <= 0xdfbf) { /* 11011111 10111111 */
7.             if(p[-1] == c >> 8)
8.                 return p - 1;
9.             else
10.                 return my_strrchr(s, c - (p - 1 - s), len - (p - 1 - s));
11.         } else {
12.             if(*((int*)(p-3)) == c)
13.                 return p - 3;
14.             else
15.                 return my_strrchr(s, c - (p - 3 - s), len - (p - 1 - s));
16.         }
17. }

Это просто набросок кода, чтобы пояснить идею. Рекурсия здесь легко заменяется циклом, я её использовал исключительно для большей понятности. Если сильно волнует производительность, то расставляем везде likely и unlikely, указывая компилятору, что скорее всего мы будем искать однобайтовые символы, и скорее всего если уж мы нашли что-то, то это то, что надо. Правда если производительность очень критична, то не надо забывать о том, что при работе с utf8 количество итераций цикла зависит от количества байт в строке, в то время как при использовании кодировок с фиксированной длинной символа, количество итераций будет зависеть от количества символов. Хотя если "тем более что наиболее вероятно будут использоваться Latin-1 в основном...", то это различие несущественно.

С utf8 можно провернуть практически всё то же самое, что и с однобайтовой кодировкой, причём не намного сложнее. Самое серьёзное что нельзя -- это быстро найти символ по номеру. Но строки обычно обрабатываются последовательно, и без этого вполне можно обойтись.

 

Rel

Любой с фиксированной длиной символа.

r90

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

 

CyberManiac

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

ps. Хватит тут играть тролля. Речь идёт не о том, какую структуру данных выбрать для работы со строками, но о выборе кодировки. Если тема реализации основных строковых операций тревожит ваш разум и выводит его из равновесия, давайте поговорим об этом. Создайте топик в wasm.heap, там мы с удовольствием обсудим влияние производительности обработки строк на психическое состояние кибернетических маньяков.

 

r90

Их уже 60 лет как складывают в сотнях и тысячах языков программирования. И в этом заключена сермяжная правда: складывать - надо. Смиритесь.

Вам интересно - вы и ищите. Хлеб за брюхом не ходит.

В нормальных кодировках длина строки в байтах получается умножением длины строки на длину символа. В угрёбищных кодировках длина строки в байтах _не_ получается умножением длины строки на длину символа.

Не могу отказать себе в удовольствии ткнуть пальцем в заголовке темы, где как бы русским языком написано: "как лучше хранить строки". И ни единого слова "о выборе кодировки", хе-хе-хе.

 

CyberManiac

То есть ваши утверждения основаны лишь на непоколебимой вере в свою правоту, и, таким образом, совершенно голословны? Именно так я и думал.

 

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

Особенно злой случай - когда заранее неизвестно, у каких токенов потребуется знать длину, когда это станет понятно в процессе разработки интерпретатора.

 

Dmitry_Milk

Теперь надо ещё помножить и поделить.