highlight.js 2.0

Это, что называется, "вштырило" :-). Новая версия highlight.js меня так впечатлила (в особенности процесс ее производства), что заслужила в моих глазах сразу "мажорного" скачка после последних изменений:

• Стараниями Антона Ковалёва появилась поддержка Ruby. Я обычно радуюсь, как ребенок, когда мне присылают языки, в которых я ничего не понимаю, потому что это улучшает библиотечку так, как я сам бы не смог. Спасибо!

• Скорость расцветки увеличилась на порядки благодаря переписанному вчера "в едином порыве" парсингу (дальше будет подробней).

• Из-за этого же подхода получилось расцветка ключевых слов стала более корректной (в частности, теперь подсвечивается "End" в конце классов Delphi).

• Расцветка Delphi, как оказалось, вообще был сломана в паре мест (не допускала символ * в коде, например :-) ). Починил.

Дальше — подробности для интересующихся Javascript'ом.

Предыстория

Серия событий, приведших к переписыванию парсинга, началась, когда я наткнулся на ответ в "Книге жалоб и предложений" Королевства Delphi о том, почему highlight.js не стоит использовать там:

Очень долго парсит, особенно под Оперой, 500 строчек текста секунд 30 обрабатывает, при этом проц загружен на 100%. К тому же там явно есть ошибки, выделяются не все слова (у меня например end в объявлении класса никогда не выделяется жирным) и по моему нет поддержки асма.

Действительно, все справедливо. Баг с невыделением end я записал "на подумать", а скорость решил не трогать, потому что для моих применений — короткие фрагменты в блоге — она была, в общем-то, приемлемой. Тем не менее, где-то глубоко в мозгу по поводу скорости "осадок остался": было что-то кардинально неправильное в том, что время обработки каких-то нескольких строчек вообще так заметно. При нынешних-то скоростях процессоров...

Потом Антон Ковалёв прислал Ruby, и я решил, что будет неплохо заодно и Delphi починить для выпуска новой версии.

Финалом серии событий стала оброненная вчера в разговоре с одним питонщиком фраза по поводу highlight.js, что это ж, мол, Javascript, конечно он медленный будет... Я решил подумать :-)

Хак

Сначала мне пришло в голову, что довольно много времени код проводит в проверках, является ли очередное слово ключевым словом языка. Ключевые слова у меня задавались простым списком:

keywords: ['else', 'for', 'if', 'while']

И он был отсортирован по алфавиту, чтобы по нему можно было искать бинарным поиском. Однако его можно очень просто заменить на поиск по хеш-таблице, который быстрее. В Javascript'е в виде хеш-таблицы можно использовать любой объект, потому что при обращении к его свойствам они ищутся как раз по хешу и делается. В итоге keywords превращаются в такого аккуратного крокодильчика:

keywords: {'else': 1, 'for': 1, 'if': 1, 'while': 1}

Теперь достаточно спросить if (keywords[some_word]), который если такое свойство есть, быстро отдаст "1", что то же самое, что "true" (само слово "true" я решил не использовать, чтобы место в исходнике не занимать, там этих keyword'ов — толпа :-)).

На моем тестовом примере, где включены все поддержанные языки, скорость обработки сократилась с 3 секунд до 2,7. 10% — в общем-то неплохо для простого изменения.

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

• keyword или нет
• начало другого режима расцветки ("строка", "комментарий")
• конец текущего режима расцветки
• недопустимая для языка конструкция

Классы в Delphi у меня начинаются на "= class" и заканчиваются на "end;". И когда вот этот "end;" появляется на проверке, он правильно определяется как конец класса, но в нем самом keyword'ы уже не ищутся, поэтому часть "end" (без точки с запятой) не подсвечивается. Чтобы их подсветить, используя уже написанную логику, пришлось бы внутри этих ограничительных выражений тоже организовывать повторный парсинг. А это выглядит слишком тяжеловесно, да и не получалось по другим причинам (пришлось бы для них определять отдельные мини-языки, что вообще ни в какие ворота).

И вот тогда я придумал переделать парсинг по-другому:

• последовательным обходом выкусываются только начала и концы режимов, keyword'ы игнорируются
• выкусанные начала, концы и содержимое режимов парсинга собираются в одну строку
• внутри этой строки организуется отдельный парсинг, который понимает только keyword'ы и ничего больше

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

После часа-другого интеллектуального раздирания парсинга он заработал, и желаемая корректность была достигнута. Но вот такого прироста скорости, который это дало, я никак не ожидал. Хотя теоретические надежды были, но я даже сомневался в начале, не будет ли на практике вообще замедления от повторных обходов.

Но на самом деле, скорости есть от чего расти.

• Раньше проверка на тип очередного выкусанного кусочка делалалась для каждого идентификатора, а также для всего whitespace с мусором между ними, потому что функция, которая выдавала кусочки, по сути своей не могла понять его природы, и приходилось всегда делать повторную проверку. Теперь эти повторные проверки делаются только для концов режимов, которых значительно меньше, чем рядовых лексем.

• Регулярки начала и конца режимов у меня так задаются, что для их поиска приходилось вырезать из общей строки ее оставшуюся часть от текущей позиции, чтобы применять регулярку от начала строки. И это происходило очень часто, на каждую лексему, и эти частые substr'ы тоже, я подозреваю, сильно тормозили дело. Теперь, когда keyword'ы вынесены отдельно, я могу их обрабатывать "глобальной" регуляркой (с опцией "g"), которая умеет работать на одной копии строки последовательно с любого ее места.

• При парсинге только keyword'ов, когда не мешаются начала и концы режимов, я точно знаю, где находится whitespace с мусором между идентификаторами, и могу для него не вызывать проверки на keyword.

• В режимах, где keyword'ов нет (строки, комментарии, цифры), поиск по ним можно вообще не запускать.

И вот итог: delphi'йский код из 502 строк расцвечивается у меня в Firefox 2 вообще незаметно глазу.