Слияние DOM-деревьев на Javascript'е

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

Мне, вообще-то, кажется, что это уже где-то есть написанное, но вчера моё Google-fu меня подвело. Поэтому я отчасти надеюсь, что мне кто-нибудь покажет, как это правильно делается.

Внимание! Это загрузочный пост для суровых javascript'овых кодеров :-).

История

Исторически highlight.js отказывался подсвечивать фрагмент кода, в котором уже есть пользовательская разметка. Делалось это по двум причинам:

• Пользовательское форматирование может конфликтовать с расцветкой. Например пользователь захотел что-то выделить в коде жирным, а расцветка взяла, и выделила жирным все keyword'ы.

• Это в общем случае ни фига не просто. Поскольку пользовательская разметка может быть какой угодно, то может оказаться, что она наложится на расцветку совсем не по правилам вложенности. Вот пример, где посреди CSS'а вставлен какой-нибудь иллюстративный <del>, начинающийся в середине цифры, которая при расцветке обернётся в <span class="value">:

  .div {
      width: 500px; margin-left: 20px;
  }

Однако где-то в феврале Владимир Долженко убедил меня, что обе проблемы имеют решение. Первая решается тем, что у пользователя уже есть средство отключить подсветку классом "no-highlight", поэтому разрешая подсветку по умолчанию, мы никого свободы не лишаем. Про вторую проблему он прислал патч, который так до вчерашнего дня у меня в почте и лежал. Сам патч, в итоге, я так и не взял, потому что он довольно сильно вмешивался в общую механику парсинга, и я, говоря по-простому, так и не смог его уместить в голове, код получался слишком сложный. Поэтому вчера я по мотивам этой идеи написал отдельную постобработку.

Слияние деревьев

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

Чтобы это реализовать, я сначала представил деревья в виде плоской "ленты событий":

• символ 5, начался элемент <p>
• символ 10, начался элемент <em>
• символ 12, кончился элемент <em>
• символ 25, кончился элемент <p>

Внутри одного DOM-дерева гарантируется правильная вложенность (оно, в конце-концов, дерево!). Делается это вот таким кодом:

function nodeStream(node) {

  // рекурсивная функция обхода childNodes
  // складывает результаты в общий массив result
  function _(node, result, offset) {
    for (var i = 0; i < node.childNodes.length; i++) {

      // текстовые node'ы только увеличивают смещение
      if (node.childNodes[i].nodeType == 3)
        offset += node.childNodes[i].nodeValue.length;
      else if (node.childNodes[i].nodeName == 'BR')
        offset += 1

      // все остальные ноды добавляются в список
      else {
        result.push({
          event: 'start',
          offset: offset,
          node: node.childNodes[i]
        });
        offset = _(node.childNodes[i], result, offset)
        result.push({
          event: 'stop',
          offset: offset,
          node: node.childNodes[i]
        });
      }
    }
    return offset;
  }
  var result = []
  _(node, result, 0)
  return result;
}

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

function nodeText(node) {
  var result = '';
  for (var i = 0; i < node.childNodes.length; i++)
    if (node.childNodes[i].nodeType == 3)
      result += node.childNodes[i].nodeValue;
    else if (node.childNodes[i].nodeName == 'BR')
      result += '\n';
    else
      result += nodeText(node.childNodes[i]);
  return result;
}

Дальше эти потоки объединяются вместе примерно по такому алгоритму:

1. Из двух потоков выбрать событие, которое случилось раньше по offset'у. При одинаковом offset'е более ранними считаются закрывающие теги, потому что выгоднее от них быстрее избавляться.

2. Открывающися тег вписывается в результирующую строку и складывается в стек "наверх".

3. Закрывающий тег:

   1. Закрывает все теги сверху стека, пока не найдёт свой парный открывающий. При правильной вложенности он сам гарантированно был бы наверху стека, но у нас это не так.

   2. Убирает себя из стека.

   3. Идёт обратно наверх стека по пути переоткрывая все теги, которые были в него вложены.

4. Повторять, пока не кончатся оба потока.

И где-то там в середине этого ещё куски исходной строчки добавляются между тегами.

Вот код:

// получает два потока и строку чистого текста
function mergeStreams(stream1, stream2, value) {
  var processed = 0;  // счётчик пройденных символов
  var result = '';    // результирующая строчка
  var nodeStack = []; // стек вложенности тегов

  // вспомогательная функция выбора потока с более ранним событием
  function selectStream() {

    if (stream1.length && stream2.length) {
      // оба потока не пустые
      if (stream1[0].offset != stream2[0].offset) 
        // если смещения не равны, выбрать меньшее
        return (stream1[0].offset < stream2[0].offset) ? stream1 : stream2;
      else
        // если равны, выбирается закрывающий
        return (stream1[0].event == 'start' && stream2[0].event == 'stop') ? stream2 : stream1;
    } else {
      // если один из потоков пустой, возвращается оставшийся
      return stream1.length ? stream1 : stream2;
    }
  }

  // вспомогательная функция формирования открывающего тега для node
  function open(node) {
    var result = '<' + node.nodeName.toLowerCase();
    for (var i = 0; i < node.attributes.length; i++) {
      result += ' ' + node.attributes[i].nodeName.toLowerCase()  + '="' + escape(node.attributes[i].nodeValue) + '"';
    }
    return result + '>';
  }

  // вспомогательная функция формирования закрывающего тега для node
  function close(node) {
    return '</' + node.nodeName.toLowerCase() + '>';
  }

  // основной цикл, пока хотя бы один поток не пуст
  while (stream1.length || stream2.length) {

    // выбирается ближайшее теговое событие, и всё до него добавляется в результат
    var current = selectStream().splice(0, 1)[0];
    result += escape(value.substr(processed, current.offset - processed));
    processed = current.offset;

    if ( current.event == 'start') {

      // открывающий тег добавляется в результат, элемент попадает в стек
      result += open(current.node);
      nodeStack.push(current.node);
    } else if (current.event == 'stop') {

      // закрывающий тег бежит по стеку, закрывая теги, пока не найдёт себя
      var i = nodeStack.length;
      do {
        i--;
        var node = nodeStack[i];
        result += close(node);
      } while (node != current.node);

      // найдя, удаляет себя из стека и бежит обратно переоткрывая закрытые теги
      nodeStack.splice(i, 1);
      while (i < nodeStack.length) {
        result += open(nodeStack[i]);
        i++;
      }
    }
  }
  result += value.substr(processed);
  return result;
}

Вот, собственно, и всё. Буду рад комментариям!