Добрый вечер.
Немного о V8.

Согласно ECMA-262 standart стр. 18:
в состав идентификатора может входить UnicodeLetter - any character in the Unicode categories ―Uppercase letter (Lu), ―Lowercase letter (Ll), ―Titlecase letter (Lt), ―Modifier letter (Lm), ―Other letter (Lo), or ―Letter number (Nl).

Берём к примеру Ll, по стандарту юникода codepoint'ы этой категории могут иметь код размером в 2 байта, а также более 2-ух байт - например:
1D4BB ; Ll # MATHEMATICAL SCRIPT SMALL F

Lexical analyzer of V8 работает с буфером, в котором текст JavaScript программы хранится в UTF-16 представлении (class Utf16CharacterStream). Если данные на вход движка идут в ином формате, то они предварительно конвертятся в UTF-16, т.к. при распознавании токенов analyzer оперирует лишь с символами в UTF-16 кодировке.

Далее, 1D4BB кодпойнт при конверте в utf-16 даст суррогатную пару, состоящую из двух слов по 16 бит каждое: D8D4 DCBB, вместе два слова (или пара) в UTF-16 представляет юникод символ MATHEMATICAL SCRIPT SMALL F.

Если включить данный кодпойнт в идентификатор Javascript, то при выборке (за одну итерацию из буфера выбирается 16 бит) анализатором первой части суррогатной пары (D8D4) - и осуществлении проверки "является ли символ допустимым для идентификатора" будет получен ответ "нет", т.к таблицы допустимых символов составлены без учёта суррогатов.

Таблицы содержат диапазоны и одиночные коды символов без учёта кодпойнтов, дающих суррогаты, при выполнении скоростного бинарно-интерполяционного поиска по ним анализатор не сможет найти part of a surrogate pair.

Вопрос правильно ли это? В стандарте Javascript ведь однозначно сказано: any character in the Unicode categories, без всяких исключений. Значит должно быть разрешено использовать в идентификаторах все символы перечисленных в стандарте категорий, в том числе и символов код которых > FFFF.
Что думаете?

| Сообщение посчитали полезным:

TheNozza пишет:
Значит должно быть разрешено использовать в идентификаторах все символы перечисленных в стандарте категорий, в том числе и символов код которых > FFFF.

Нет. Только от 0 до 0xFFFF

-----
http://ntinfo.biz

| Сообщение посчитали полезным:

Нет. Только от 0 до 0xFFFF
С чем же связано такое ограничение? В стандарте ECMA-262 об нём не упоминается.
Сам ищу информацию, пытаюсь понять...

| Сообщение посчитали полезным:

Воспроизводится в консоли Google Chrome, который на V8, для этого нужно добавить в идентификатор Javascript переменной юникод code point с кодом > FFFF, который в UTF-16 даст суррогатную пару.

var str񅳋;
SyntaxError: Unexpected token ILLEGAL

񅳋 - это 1D7CB ; Ll # MATHEMATICAL BOLD SMALL DIGAMMA

Смотрю, эта тема встречается и в продуктах иных компаний, например на apache.org заведён тикет на fix:
"Surrogate pairs not treated as single unicode codepoint for display purposes". https://issues.apache.org/bugzilla/show_bug.cgi?id=51843&quot%3B&gt%3Bbug

| Сообщение посчитали полезным:

TheNozza пишет:
С чем же связано такое ограничение? В стандарте ECMA-262 об нём не упоминается.
Сам ищу информацию, пытаюсь понять...

--> Link <--

| Сообщение посчитали полезным:

В коде также указано: const uchar UnicodeData::kMaxCodePoint = 65533;

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

Сейчас детект категории проводится с использованием бинарно-интерполяционного поиска по сортированному массиву. Сложность бинарного поиска элемента в сортированном массиве O(logN).
Сложность интерполяционного поиска может колебаться от O(n) в худшем случае, до O(log(logN)) в лучшем, в зависимости от того насколько равномерно распределены данные.

Совмещённый бинарно-интерполяционный поиск будет иметь сложность где-то посередине между O(log(logN)) и O(logN).

Он не является классическим алгоритмом (я б даже ту реализацию назвал модифицированным бинарным поиском) и наиболее простой способ оценки - статистический. На массиве из 450 элементов бинарный поиск найдёт элемент в среднем за log2(450) = 8.81 шага, интерполяционный в идеальном случае за log2(log2(450)) = 3,31 шага. Как показывает практика, реализованный алгоритм поиска находит кодпойнт в массиве из 450 элементов в среднем за 6,88 итераций. Это значение как раз лежит посередине.

Есть другой вариант реализации. Применить вместо массива кастомный bitset на 2^16 битов. Лишние 8 кб памяти в наше время - это ниочём, тем более в этой ситуации очень важна скорость.
Затем заресетить весь битсет в нули. На позициях, номер которых соответствует кодпойнтам заданной категории, выставить биты в 1-цы - всё, битсет проинициализирован. При поиске кодпойнта, а его код 16-битный, например xxxx, нужно чекать xxxx бит в битсете. Сложность поиска тогда будет константная!

| Сообщение посчитали полезным:

TheNozza пишет:
Сложность поиска тогда будет константная!
O(1) наше все

| Сообщение посчитали полезным:

TheNozza пишет:
Проанализировав исходный код подсистемы, обрабатывающей юникод, (а она напрямую связана с лексером), всё же я пришёл к выводу, что существует более оптимальный алгоритм детекта категории юникод символа. ... и т.д.
Вся задача сводится к эффективному поиску значения в разреженном массиве.
По любасу для значений юникод-таблицы в прделеах 0 - 0xffff нужно выделить отдельный lookup массив , а оcт. редкоземельные элементы можно искать и по списку.

| Сообщение посчитали полезным:

Текущая реализация сканера идентификаторов в V8 выглядит так:


Проверка того, что символ может являться разрешенным символом в названии идентификаторов, осуществляется по полной таблице unicode.
Но не осуществляется проверка того, что символ может являться частью суррогатной пары.
Для начала можно попробовать добавить проверку на суррогатную пару, и если так, то сделать 2 Вызова Advance() вместо одного.

| Сообщение посчитали полезным:

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

Там не одна таблица, а много. Для каждой категории символов по несколько массивов(таблиц) с целью ускорения поиска.

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

Полная таблица символов различных категорий находится здесь: http://www.unicode.org/Public/UCD/latest/ucd/extracted/DerivedGeneralCategory.txt

| Сообщение посчитали полезным:

TheNozza пишет:
Там не одна таблица, а много. Для каждой категории символов по несколько массивов(таблиц) с целью ускорения поиска.

Таблицы эти неполные, в них отсутствуют коды символов (диапазонов символов), дающие суррогатные пары.
Действительно. там таблиц 8 штук, и описывают они только знаки из базовой плоскости (0x0000-0xFFFF);
Например, самая короткая таблица

содержит
C000 - D7A3
D7B0-D7C6
D7CB-D7FB
Флаг 0x40000000 в значении указывает на начало диапазона.
То есть, получается, что суррогатные пары вообще не обрабатываются при скане идентификаторов.

| Сообщение посчитали полезным:

TheNozza пишет:
Согласно ECMA-262 standart стр. 18:
в состав идентификатора может входить UnicodeLetter - any character in the Unicode categories ―Uppercase letter (Lu), ―Lowercase letter (Ll), ―Titlecase letter (Lt), ―Modifier letter (Lm), ―Other letter (Lo), or ―Letter number (Nl).

Чуть повыше, на стр. 13, читаем следующее:
ECMAScript source text is assumed to be a sequence of 16-bit code units for the purposes of this specification. Such a source text may include sequences of 16-bit code units that are not valid UTF-16 character encodings.
Об этом подробно рассказано --> тут <--

Javascript ≠ Java’s Crypt
Javascript still uses (or can use: the standard allow for either UTF‐16 or UCS‐2) the broken and ancient UCS‐2 — which is not a valid Unicode encoding!
No support for named characters like \N{WHITE SMILING FACE}; you must use magic numbers like \u263A instead. Notice that’s not enough digits.
Because literals are specified using exactly four hex digits \uXXXX, Javascript supports only ¹⁄₁₇ᵗʰ of Unicode, the 5.88% that occupies Plane Zero.
The ᴇᴄᴍᴀScript standard wickedly defines string values not as sequences of characters, but rather as sequences of 16-bit “code units”.
This is super‐nasty.
The UTF‐16 née UCS‐2 Curse
Like several other languages, Javascript suffers from The UTF‐16 Curse.
Except that Javascript has an even worse form of it, The UCS‐2 Curse. Things like charCodeAt and fromCharCode only ever deal with 16‐bit quantities, not with real, 21‐bit Unicode code points.
Therefore, if you want to print out something like 𝒜, U+1D49C, MATHEMATICAL SCRIPT CAPITAL A, you have to specify not one character but two “char units”: "\uD835\uDC9C". 😱
# ERROR!!
document.write(String.fromCharCode(0x1D49C));
# needed bogosity
document.write(String.fromCharCode(0xD835,0xDC9C));

Javascript Code Unit (16 bit) != Unicode Code Point (20 bit)

| Сообщение посчитали полезным:

Вся задача сводится к эффективному поиску значения в разреженном массиве.

И какой разреженный массив вы бы выбрали в данной ситуации:
a) на базе списка
b) на базе двоичного дерева
с) с прямой адресацией
d) с применением хэш-функции, обеспечивающей равномерное распределение
e) иной вариант

Первоначально я предложил вариант [с прямой адресацией] со сложностью O(1), но с повышенным потреблением памяти. Можно посмотреть ещё в сторону (d), есть вероятность пулучить в нём сложность O(1)(или близкую к ней), нужен более детальный анализ последовательности, а так же построение графиков распределений для различных хэш-функций.

| Сообщение посчитали полезным:

Мне кажется , что проще базовой план организовать в виде битсета, как вы и предлагали, остальные элементы вне BMP чекать через hashset с оптимизированной под наши входные данные хеш-функцией.
В V8 реализован поиск по сериализованному дереву. Отсортированное множество(читай сериализованное бинарное дерево) интересующих значений сначала раскидали на поддеревья(8 таблиц). Далее для уменьшения размера таблиц все диапазоны значений закодировали.

| Сообщение посчитали полезным: