Yet Another cSS selector = YASS

После заметки о Peppy я почти обрадовался — вот оно, счастье. Наконец появился движок CSS-селекторов, который делает тоже самое, что и jQuery, только быстрее. Сильно быстрее.

Радоваться было недолго, как только я посмотрел в код, то немного ужаснулся: он не соответствовал моим представлениям об исключительной производительности. Совсем не соответствовал. Точнее, немного удовлетворял, но не до конца. Поэтому сразу встал вопрос: а если быстрее?

Почему нельзя сделать быстрое мини-ядро для CSS-селекторов, которое обеспечит базовую функциональность для работы с DOM (ну, совсем базовую — просто выборку элементов, например)? И, самое главное, чтобы это работало не медленнее (в идеале, даже быстрее), чем нативные вызовы.

Основы быстродействия

Ну, подумали и сделали. После двух бессонных дней ночей удалось набросать простой движок для выбора элементов по CSS1-селекторам (попутно был отброшен XPATH как на порядок более медленная технология и осознано, почему jsForms также работают несколько медленнее, чем встроенные DOM-методы браузера).

Во-вторых, такой код должен и кэшировать выборки (DOM-вызовы дорого обходятся, все нормальные JavaScript-программисты уже их кэшируют — так упростим им задачу и повысим быстродействие).

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

В-четвертых, библиотека должна возвращать сами элементы, чтобы к ним можно было «прикрутить» любые обертки и нарастить методы. Все обертки ресурсоемки. Если нужно просто 200 раз поменять HTML на странице у заданных элементов, то они не нужны. Достаточно и проверок со стороны браузера на допустимость выполняемых операций.

В-пятых, естественно, библиотека должна опираться на все самое быстрое: быстрые итераторы, быстрые подстановки, анонимные функции, минимум вложенных вызовов и т.д.

Код

В качестве лучшей иллюстрации приведу сам код (он доступен и на тестовой странице YASS), ибо его немного (это же мини-ядро, все-таки, сорри за подсветку, не очень легкочитаемо получилось):

/* открываем анонимную функцию */
(function(){
/* объявляем локальную переменную, затем ее переведем в window. Переменная называется _
-- нет конфиликтов с текущими реализациями подобного функционала через $ */
var _ = function () {
/* кэшируем вызов для document */
  var doc = document,
/* получаем сам селектор в качестве первого аргумента */
    selector = arguments[0],
/* и возможность использования кэша во втором */
    nocache = arguments[1];
/* возвращаем элемент из кэша, если получается*/
  if (_.cache[selector] && !nocache) {
    return _.cache[selector];
  } else {
/* пробуем применить querySelectorAll, работает сейчас только в Safari */
    if (doc['querySelectorAll']) {
      _.nodes = doc['querySelectorAll'](selector);
    } else {
      switch (selector) {
/* обрабатываем несколько элементарных случаев. Например, body */
        case 'body':
          _.nodes = doc.body;
          break;
/* или head для страницы */
        case 'head':
          _.nodes = doc['getElementsByTagName']('head')[0];
          break;
        case 'a':
          _.nodes = doc.links ? doc.links : doc['getElementsByTagName']('a');
          break;
        case 'img':
          _.nodes = doc.images ? doc.images : doc['getElementsByTagName']('img');
          break;
/* самый общий случай, можно еще ускорить */
        default:
/* по отдельности рассматриваем селекторы, разделенные запятыми */
          var groups = selector.replace(/, +/g,",").split(","),
            groups_length = groups.length - 1;
            j = -1;
/* везде используем while, а не for -- так быстрее */
          while (j++ < groups_length) {
/* каждый такой селектор разбиваем на группы, которые содержат узлы тэг-id-класс */
            var singles = groups[j].split(' '),
              singles_length = singles.length - 1,
              i = -1,
              level = 0;
/* в качестве начала поиска нужного узла устанавливаем сам документ */
            _.nodes = doc;
            while (i++ < singles_length) {
/* применяем быстрый разбор регулярного выражения с применением параметров
(тэг-id-класс), подробнее:
webo.in/articles/habrahabr/40-search-not-replace
*/
              singles[i].replace(/([^\.#]+)?(#([^\.#]+))?(\.([^\.#]+))?/, function(a, tag, b, id, c, klass) {
/* проверяем, задан ли только id (и при этом еще не спустились дальше корня документа) */
                if (tag == '' && klass == '' && !level) {
                  _.nodes = doc[/*@cc_on !@*/0 ? 'all' : 'getElementById'](id);
                } else {
/* теперь проверяем, задан ли только тэг */
                  if (klass == '' && id == '' && !level) {
                    _.nodes = doc['getElementsByTagName'](tag);
/* а потом уже запускаем общий механизм отбора узлов по тэгу, id и классу */
                  } else {
/* массив, в который будет складывать результаты */
                    var newNodes = {},
/* кэшируем текущий размер массива */
                      nodes_length = _.nodes.length,
                      J = -1,
/* кэшируем итератор, в который будем складывать новый размер массива */
                      idx = 0;
/* если в качестве корневого элемента передан 1 элемент, то делаем из него массив
для перебора */
                    if (!nodes_length) {
                      _.nodes = [_.nodes[0]?_.nodes[0]:_.nodes];
                      nodes_length = 1;
                    }
/* опять while, а не for-in или for */
                    while (J++ < nodes_length) {
                      var node = _.nodes[J];
                      if (node) {
/* находим все тэги */
                        var childs = node['getElementsByTagName'](tag ? tag : '*'),
                          childs_length = childs.length,
                          h = -1;
                        while (h++ < childs_length) {
                          var child = childs[h];
/* проверяем их на соответствие заданным id или классу */
                          if (child && (!id || (id && child.id == id)) && (!klass || (klass && child.className.match(klass)))) {
/* и только после этого записываем в результирующий массив */
                            newNodes[idx++] = child;
                          }
                        }
                      }
                    }
/* теперь записываем в текущие узлы все выбранные на данном этапе */
                    _.nodes = newNodes;
          _.nodes.length = idx - 1;
                  }
                }
/* "грязный" хак для обозначения "корня" для текущей выборки --
можем ли использовать "быстрые" выборки по тегу или id или нужен общий подход */
                level++;
              });
/* теперь вбрасываем все узлы от одного селектора в боле глобальный массив --
на тот случай, если у нас задано несколько селекторов через запятую */
              if (groups_length) {
                var nodes_length = _.nodes.length,
                  K = -1,
                  idx = _.sets ? _.sets.length : 0;
        _.sets = _.sets ? _.sets : {};
                while (K++ < nodes_length) {
                  _.sets[idx++] = _.nodes[K];
                }
                _.sets.length = idx;
/* иначе просто копируем текущую выборку элементов в более глобальный массив */
              } else {
                _.sets = _.nodes;
              }
            }
          }
          break;      
      }
    }
/* проверяем, есть ли у нас глобальная выборка. Если нет, то копируем локальную в нее
немного дублирует чуть выше написанный код. Надо отрефакторить */
  _.sets = _.sets ? _.sets : _.nodes;
/* сохраняем результат в кэше, следим за тем, чтобы сохранилась ссылка на элемент */
    _.cache[selector] = _.sets.length>1||_.sets.nodeName ? _.sets : _.sets[0];
/* очищаем все использованные переменные для предотвращения утечек через ссылки на DOM
-- еще нужно проверить, если ли в IE утечки при этом */
  _.sets = _.nodes = null;
/* ну и возвращаем полученный результат */
    return _.cache[selector];
  }
};
/* текущий набор узлов */
_.nodes = null;
/* более глобальный набор узлов, соединяющий несколько селекторов, разделенных запятой */
_.sets = null;
/* кэш для выбранных узлов */
_.cache = {};
/* а вот только теперь записываем как единственную глобальную переменную: window._ */
window._ = _;
})();

Примеры вызовов

Все до безобразия просто:
_('p') — вернет все параграфы на странице
_('p a') — или все ссылки в них
_('p a.blog') — или все ссылки с классом blog
и т.д. Полная CSS1 гамма.

Еще один велосипед?

Может быть, кому-то данный случай покажется тривиальным, но мне лично дальнейшее развитие ситуации видится следующим образом. Либо код можно использовать в образовательных целях, что понять логику конечных автоматов, используемых браузером для распознавания CSS-селекторов (во встроенном движке), и промоделировать некоторые тривиальные или не очень ситуации.

Или же данный код можно будет доработать и включать в основу высокопроизводительных библиотек, которые уже будут на него наворачивать свои методы. Как легко видеть, код замечательно расширяемый или даже модульный. Все, что ему требуется, — это браузер :)

В качестве заключения

В ближайшее время я планирую провести ряд исследований, какова производительность различных методов и подходов в JavaScript — ведь именно за ним будущее (веб-) приложений. И CSS-селекторы пока (и еще долгое время будут, до внедрения в IE querySelectorAll) являются одним из «китов» построения любого приложения. И чем шустрее этот кит получается, тем быстрее работает все остальное.

Текущая версия YASS (читается как yeasss! :) — 0.1. Развиваться будет. Текущий размер кода: около 6 Кб со всеми комментариями, 1,5 — минимизированная версия и 650 байтов — архив с ней. Вдумайтесь: 650 байт пожатого кода, чтобы выбрать любой элемент на странице с помощью CSS1 селекторов. И выбрать почти что не медленнее (разница составляет -10… +30% от нативных методов — за счет кэширования), чем с помощью прямых методов.

Тестирование грядет. Пока что текущая реализация быстрее чем Peppy в полтора-два раза, который и так всех обгоняет.

P.S. В общем, как и ожидалось, yass сильно быстрее текущих библиотек. Только вот тесты проваливает :)
Спасибо lusever за тестовое окружение. Результаты можно посмотреть здесь