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

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

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

История

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

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

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

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

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

Внутри одного 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;
}

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

Комментарии: 10

  1. Alik Kirillovich

    Спасибо, буду разбираться.

    Пока замечание по форме:

    Рекурсивная функция «_» выглядит не слишком симпатично.

    Если она используется только один раз по месту объявления, то лучше преобразовать в анонимную рекурсию:

    (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 = arguments.callee (node.childNodes[i], result, offset)
          result.push({
            event: 'stop',
            offset: offset,
            node: node.childNodes[i]
          });
        }
      }
      return offset;
    })(node, result, 0)
    
  2. Ivan Sagalaev

    Если она используется только один раз по месту объявления, то лучше преобразовать в анонимную рекурсию:

    Doh! Спасибо за совет, не очень теперь понимаю, почему так не сделал :-).

  3. Игорьбек

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

    Понимаю, что задача решалась в общем виде, для сохранения вложенности, но, мне кажется, что открываться/закрываться должен как раз таки поток подсветки, т.к. там всегда гарантировано, что элементы inline'овые.

  4. Михаил

    ну и еще один вариант описания рекурсии через именованное замыкание:

    (function me(node, result, offset) {
        // skip
    
        me(node.childNodes[i], result, offset);
    
        // skip
    })(node, result, 0);
    
  5. Макс Лапшин

    Ваня, я такую штуку делал в 2005 году для очень специфичного языка разметки.

    В твоем коде не хватает приоритетов. Ссылка является более приоритетной штукой, чем стронг, поэтому если сейчас открыт стронг и начинается ссылка, то стронг надо закрыть, убрать в стек, ссылку открыть, из стека достать закрытый стронг и открыть его обратно.

  6. Ivan Sagalaev

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

    Это я виноват, что в картинке зачем-то <p> написал. Поскольку речь у меня идёт о внутренностях элемента <code>, то там гарантированно всё inline.

  7. Ivan Sagalaev

    Макс, почему ссылку нельзя делать внутри <strong>? Всё будет вполне нормально работать.

  8. CTAPbIu_MABP

    да, Макс Лапшин, абсолютно прав
    например плохим стилем является помещение блочных элементов в строчные <span><h2>some text<h2></span>

  9. http://maxidoors.ru/

    На практике оказалось, что это рвет внешность. Плюс H2 должен быть вне стронга.

  10. [...] Слияние DOM-деревьев на Javascript New [...]

Добавить комментарий