Осваиваем HTML5: обход дерева

Russian (Pусский) translation by AlexBioJS (you can also view the original English article)

Одна из наиболее важных концепций DOM – обход дерева (* процесс единоразового посещения (проверки и/или обновления) каждого узла дерева (структура данных). Здесь и далее примеч. пер.). Поскольку теория вычислительных машин и систем (* компьютерные науки; общее название для совокупности дисциплин, связанных с конструированием компьютеров и их использованием в обработке информации. Объединяет теоретические и практические аспекты многих наук, таких как электроника, программирование, математика, искусственный интеллект, человеко-машинное взаимодействие, конструирование и др.) сформировалась как самостоятельная область исследований, десятилетия были потрачены на разработку структур данных (* способ хранения и организации данных для более удобного доступа к ним и обработки; может представлять собой описание полей записи, таблицы, списка, массива, файла и т. п.) и алгоритмов (* математическая функция или конечный чёткий набор описаний логической последовательности действий, необходимых для того, чтобы компьютер или интеллектуальное устройство выполнили за конечное время некоторую задачу). Одной из наиболее часто используемых структур является дерево. Деревья представлены везде. Одной из простейших и в то же время полезной и часто используемой версией дерева является двоичное дерево (* структура данных, представляющая собой дерево, каждая вершина (узел) которого имеет не более двух потомков. Каждая вершина может также содержать ключ, идентифицирующий эту вершину и ассоциированный с некоторыми данными. Двоичные деревья используются в некоторых алгоритмах сортировки и поиска данных. У двоичных деревьев различают следующие части: корень (root), левая ветвь (left branch), правая ветвь (right branch) и листья (leaf node)). Спортивное соревнование можно представить в виде двоичного дерева. Однако дерево DOM не является двоичным. Это K-арное дерево (* дерево с корнем, в каждом узле которого имеется не более k дочерних узлов). Каждый узел может иметь от нуля до N подузлов, называемых childNodes.

В дереве DOM содержится большое разнообразие всевозможных типов узлов. Это могут быть Text, Element, Comment и другие дополнительные, например ProcessingInstruction или DocumentType помимо многих других. Большинство из них не будет содержать каких-либо childNodes (* дочерних элементов) по определению (* по своей природе). Они являются конечными точками (* термин "конечная точка" (endpoint) часто используется для описания отдельной функции API) и содержат только один тип информации. Например узел Comment содержит только указанную строку комментария. В узле Text может содержаться только строка с контентом.

В узле Element содержатся другие узлы. Мы можем рекурсивно (* с повторным использованием процедуры, правила для достижения результата) спускаться к элементам для обхода всех доступных узлов дерева.

Наглядный пример

Примером, который также относится к предыдущей статье, в которой рассматривался элемент <template>, является заполнение поддерева. Поддерево – часть дерева, которая начинается с указанного элемента. Этот элемент называется корнем поддерева. Если бы мы взяли элемент <html> дерева в качестве корня поддерева, то поддерево было бы почти идентично дереву документа, которое начинается с document, то есть располагалось бы на один уровень ниже documentElement.

Для того чтобы заполнить поддерево, нам необходимо выполнить итерацию для дочерних элементов корня поддерева. Для каждого узла нам необходимо уточнить его тип и затем продолжить соответствующим образом. Например каждый элемент необходимо снова принимать в качестве корня поддерева. Узлы с текстом, с другой стороны, нужно оценивать более тщательно. Возможно нам также хочется проверить узлы с комментариями на наличие специальных директив. Более того, также необходимо рассмотреть атрибуты элементов.

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

function applyModel(model, data) {
  var rx = new RegExp('\\{\\s*(.+?)\\s*\\}', 'g');
	var group = rx.exec(data);
	
	while (group) {
		var name = group[1];
		var value = '';
		eval('with (model) { value = ' + name + '; }');
		data = data.replace(group[0], value);
		group = rx.exec(data);
	}

	return data;
}

Давайте рассмотрим реализацию вышеописанного сценария, в котором используется метод applyModel в различных ситуациях. Этот метод принимает образец элемента template и объект model для возвращения нового DocumentFragment. В новом фрагменте используются данные из модели для изменения всех значений {X} на результат вычисления выражения X, при котором использовался предоставленный объект.

function iterateClassic (template, model) {
	var fragment = template.content.clone(true);
	var allNodes = findAllNodes(fragment);

	allNodes.forEach(changeNode);
	return fragment;
}

В предыдущем коде используется функция findAllNodes, которая принимает узел и сохраняет все его дочерние элементы в массиве. Затем функция вызывается рекурсивно для каждого дочернего элемента. В конце все результаты помещаются в единственный массив для всего поддерева, то есть мы преобразуем дерево в одномерный массив.

Ниже показан фрагмент кода для одного из вариантов реализации описанного выше алгоритма.

function findAllNodes (childNodes) {
	var nodes = [];

	if (childNodes && childNodes.length > 0) {
		for (var i = 0, length = childNodes.length; i < length; i++) {
			nodes.push(childNodes[i]);
			nodes = nodes.concat(findAllNodes(childNodes[i].childNodes));
		}
	}

	return nodes;
}

Функция для изменения каждого узла массива показана ниже. Функция выполняет некоторые манипуляции в зависимости от типа узла. Нас интересуют только атрибуты элементов и текстовые узлы.

function changeNode (node) {
	switch (node.nodeType) {
		case Node.TEXT_NODE:
			node.text.data = applyModel(model, node.text.data);
			break;
		case Node.ELEMENT_NODE:
			Array.prototype.forEach.call(node.attributes, function (attribute) {
				attribute.value = applyModel(model, attribute.value);
			});
			break;
	}
}

Хотя вышеописанный код легко понять, в нем не все так гладко. У нас имеется довольно много проблем с производительностью, особенно из-за наличия как на зло необходимых операций с DOM. Наш сценарий можно реализовать более эффективно при помощи одного из вспомогательных интерфейсов дерева DOM. Обратите внимание, что метод findAllNodes возвращает массив со всеми узлами, а не только с образцами Element поддерева. Если мы заинтересованы в этом, то можем просто воспользоваться вызовом querySelectorAll('*'), при помощи которого выполняется итерация.

Итерирование (* процесс повторяющегося выполнения последовательности операторов или команд) для узлов

Сразу же находим решение проблемы – использование интерфейса NodeIterator. NodeIterator осуществляет итерацию для узлов. Он почти идеально подходит под наши требования. Мы можем создать новый NodeIterator при помощи метода createNodeIterator объекта document. Метод принимает три ключевых параметра:

Корневой узел поддерева, для которого необходимо выполнить итерацию.
Фильтры для указания узлов, которые необходимо выбрать / для которых необходимо выполнить итерацию.
Объект с методом acceptNode для фильтрации элементов на основании пользовательских настроек.

В то время как первый аргумент - лишь простой узел DOM, в качестве остальных двух используются специальные константы. Например: если необходимо, чтобы были показаны все узлы, то мы должны передать -1 в качестве фильтра. Альтернативный вариант – можем использовать NodeFilter.SHOW_ALL. Мы могли бы скомбинировать несколько фильтров различными способами. Например для показа всех узлов с комментариями и элементами можно использовать NodeFilter.SHOW_COMMENT | NodeFilter.SHOW_ELEMENT.

Третий аргумент – объект, который может выглядеть настолько просто, как показанный ниже фрагмент кода. Хотя кажется, что объект, оборачивающий функцию, лишний, его необходимо указывать таким образом. Некоторые браузера, например Mozilla Firefox, предоставляют нам возможность сокращать объект до единственной функции.

var acceptAllNodes = {
	acceptNode: function (node) { 
		return NodeFilter.FILTER_ACCEPT;
	}
};

Здесь мы принимаем любой узел, переданный в функцию. Также у нас имеется возможность отклонить узел (и его дочерние элементы) при помощи опции FILTER_REJECT. Если мы просто хотим пропустить узел, однако по-прежнему заинтересованы в его дочерних элементах, то можем воспользоваться константой FILTER_SKIP.

Реализовать наш предыдущий пример при помощи NodeIterator довольно просто. Мы создаем новый итератор (* управляющая структура, определяющая порядок выполнения некоторых повторяющихся действий, устройство или программа организации циклов) при помощи конструктора document. Затем мы используем метод nextNode для выполнения итерации для всех узлов.

Давайте взглянем на преобразованный пример.

function iterateNodeIterator (template, model) {
	var currentNode;
	var fragment = template.content.clone(true);
	var iterator = document.createNodeIterator(
	    fragment,
	    NodeFilter.SHOW_ELEMENT | NodeFilter.SHOW_TEXT,
	    acceptAllNodes,
	    false
	);

	while ((currentNode = iterator.nextNode()))
		changeNode(currentNode);

	return fragment;
}

Поиск по DOM полностью скрыт от нас. Это очень выгодно. Мы лишь запрашиваем необходимые нам узлы, остальное выполняется наиболее эффективным способом в движке браузера. Однако, с другой стороны нам по-прежнему необходимо написать код для выполнения итерации для узлов с атрибутами.

Хотя для отбора атрибутов используется константа SHOW_ATTRIBUTE, они не связаны с узлами для элементов как дочерние узлы. Вместо этого они располагаются в коллекции NamedNodeMap, поиск по которой при помощи NodeIterator не будет происходить. Мы можем выполнить итерацию для атрибутов элементов только в том случае, если мы начинаем итерацию с атрибута элемента, при этом ограничивая наш выбор только атрибутами элементов.

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

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

Обход дерева

Мы хотим выполнить итерацию для узлов в поддереве. Другой вариант для решения нашей проблемы, который можем придумать, – использование TreeWalker. При этом мы обходим дерево, как следует из имени интерфейса. Мы указываем корневой узел и элементы, которые необходимо принимать во внимание при обходе, и затем начинается обработка. Интересно то, что TreeWalker имеет много общего с NodeIterator. Это не только уже нами увиденные общие свойства, но и использование NodeFilter для установления ограничений.

В большинстве случаев TreeWalker в действительности является лучшим выбором, чем NodeIterator. API NodeIterator чрезвычайно громоздкий для тех возможностей, которые он предоставляет. У TreeWalker имеется еще больше методов и настроек, но, во всяком случае, они находят применение.

Главное различие между TreeWalker и NodeIterator заключается в том, что при использовании первого узлы поддерева представляются в виде дерева, а не списка, как в случае с итератором. В то время как NodeIterator позволяет нам перемещаться вперед или назад, TreeWalker предоставляет нам также возможность перемещения к родительскому элементу узла, к одному из дочерних элементов или к узлу-брату (* вершина дерева, имеющая того же "родителя").

function iterateTreeWalker (template, model) {
	var fragment = template.content.clone(true);
	var walker = document.createTreeWalker(
	    fragment,
	    NodeFilter.SHOW_ELEMENT | NodeFilter.SHOW_TEXT,
	    acceptAllNodes,
	    false
	);

	while (walker.nextNode())
		changeNode(treeWalker.currentNode);

	return fragment;
}

В отличие от NodeIterator TreeWalker указывает прямиком на указанный узел дерева. При перемещении узла TreeWalker будет следовать соответственно. Что более важно, – то, что при удалении из дерева узла, на который указывает TreeWalker, мы фактически окажемся за пределами дерева документа. Если мы последуем совету, данному при реализации примера за счет NodeIterator, и не будем изменять дерево при обходе, то получим тот же результат.

Также похоже, что TreeWalker почти идентичен NodeIterator при достижении наших целей. Имеются причины, по которым последний не мог бы привлечь к себе значительное внимание. Тем не менее, TreeWalker также не пользуется особой популярностью. Возможно, что область его применения слишком ограничена, поскольку отсутствует возможность обхода узлов с атрибутами, – особенно при наличии третьего варианта для выполнения итерации для дерева DOM.

Выбор диапазона

Наконец, имеется третья конструкция, которая может пригодиться при некоторых обстоятельствах. Если мы хотим выбрать диапазон значений в одномерном массиве, то можем запросто реализовать это при помощи всего лишь двух индексов: i – для начальной (левой) границы и f – для конечной (правой) границы, [i, f].

Если мы заменим массив связным списком (* список (структура данных), элементы которого не обязательно расположены в памяти последовательно. Доступ к следующему элементу (list element , node) осуществляется с помощью указателя, хранящегося в предыдущем элементе списка. У последнего элемента указатель имеет специальное значение (null pointer), по которому определяется конец списка. Список может быть однонаправленным (one-way list, single-linked list) и двунаправленным (double-linked list), когда каждый его элемент содержит ссылки как на следующий, так и на предшествующий элементы. Индексом элемента списка является порядковый номер элемента в списке), то два индекса также можно будет заменить двумя конкретными элементами, [n_i, n_f]. Преимущество при использовании этого варианта заключается в скрытом механизме обновления. Если мы добавляем в диапазон элементы, нам не нужно обновлять его границы. Также при удалении левой границы из связного списка мы получаем диапазон, увеличившийся в левую сторону, типа [0, n_f].

Что ж, у нас рассматриваемая тут проблема не связана с одномерным массивом, а с древовидной структурой. Выбор диапазона K-арного дерева не так просто осуществить. Мы могли бы придумать свой собственный алгоритм, однако в дереве DOM имеются свои «подводные камни». Например у нас имеются текстовые узлы, которые, возможно, также необходимо добавить в диапазон. В дереве DOM нашего примера диапазон состоит из четырех свойств. У нас имеется стартовый узел, конечный узел и смещение для обоих.

Также имеются хелперы, например метод selectNode или selectNodeContents, при помощи которых выполняются необходимые вызовы setStart и setEnd. К примеру вызов selectNodeContents(node) эквивалентен следующему фрагменту кода:

1	range.setStart(node, 0);
2	range.setEnd(node, node.childNodes.length);

Выбор диапазонов выполняется не только нами в коде. Это происходит и при визуальном выборе в браузере. Метод getSelection() объекта window возвращает объект Selection, который может быть запросто преобразован в Range при помощи вызова метода getRangeAt(0). Если ничего не выбрано, то при вычислении предыдущего выражения возвращается ошибка.

Давайте рассмотрим простой пример выбора диапазона, результат которого выглядит следующим образом:

Здесь диапазон начинается в текстовом узле первого элемента списка и заканчивается в конце текстового узла элемента strong. На следующем изображении показан рассматриваемый диапазон с точки зрения исходного кода:

Также интересно взглянуть на дерево DOM для рассматриваемого образца Range. Мы видим, что при помощи подобного диапазона можно выбрать все разнообразие узлов без их родительских элементов или узла-брата.

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

Извлечение – собственно внесение изменений в DOM, то есть при нем будет модифицировано существующее дерево. После манипуляций у нас остались следующие два элемента, точно так, как и ожидалось.

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

Объекту Range недостает возможности итерации, с которой мы ознакомились ранее. Вместо этого у него имеются усовершенствованные возможности сериализации (* преобразование параллельных данных в последовательные, например для передачи по последовательному каналу) и экспорта. Поэтому измененный код нашего ранее реализованного примера поначалу может показаться громоздким. Тем не менее, за счет добавления нескольких новых методов мы можем объединить гибкость Range с улучшенной итерацией.

Range.prototype.current = function () {
	if (this.started)
		return this.startContainer.childNodes[this.startOffset];
};

Range.prototype.next = function (types) {
	var s = this.startContainer;
	var o = this.startOffset;
	var n = this.current();

	if (n) {
		if (n.childNodes.length) {
			s = n;
			o = 0;
		} else if (o + 1 < s.childNodes.length) {
			o += 1;
		} else {
			do {			
				n = s.parentNode;

				if (s == this.endContainer)
					return false;

				o = Array.prototype.indexOf.call(n.childNodes, s) + 1;
				s = n;
			} while (o === s.childNodes.length);
		}

		this.setStart(s, o);
		n = this.current();
	} else if (!this.started) {
		this.started = true;
		n = this.current();
	}

	if (n && types && Array.isArray(types) && types.indexOf(n.nodeType) < 0)
		return this.next();

	return !!n;
};

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

function iterateRange (template, model) {
	var fragment = template.content.clone(true);
	var range = document.createRange();
    range.selectNodeContents(fragment);

	while (range.nextNode([Node.TEXT_NODE, Node.ELEMENT_NODE]))
		changeNode(range.current());

	range.detach();
	return fragment;
}

Несмотря на то что Range подвергается «сборке мусора» (* выполняемая во время исполнения программы операция удаления ненужных данных и переупорядочения (объединения в более крупные) блоков динамически распределяемой памяти, необходимой для дальнейшей работы. Эта операция может выполняться средствами , интерпретатора, приложения, аппаратуры - возможно, в разных их сочетаниях. Обычно запускается, когда объём свободной памяти становится меньше заранее определённого. Освобождённая память возвращается в пул свободной (доступной для распределения) памяти. Впервые сборка мусора была введена в Lisp в начале 1960-х годов), как и любой другой объект JavaScript, по-прежнему избавление от него при помощи функции detach считается устоявшейся практикой. Одна из причин – то, что все образцы Range в действительности сохраняются в document, где они обновляются при манипуляциях с DOM.

Определение наших собственных методов для Range – удачная идея. Смещения автоматически обновляются, и у нас имеются дополнительные возможности, например клонирования текущего выбранного ряда элементов в качестве DocumentFragment, извлечения или удаления выбранных узлов. Также мы можем создать API для наших собственных нужд.

Заключение

Выполнение итерации для дерева DOM – интересная тема для всех, кто интересуется манипулированием DOM и эффективным получением узлов. Для большинства возможных сценариев уже имеется соответствующий API. Нам нужно просто выполнить итерацию? Мы хотим выбрать диапазон узлов? Нас интересует обход дерева? У каждого метода имеются свои недостатки и преимущества. Если мы знаем, что нам необходимо, то можем сделать правильный выбор.

К сожалению, древовидные структуры не так просты, как одномерные массивы. Их можно превратить (* построить соответствие) в одномерные массивы, однако при этом учитываются те же алгоритмы, что и при выполнении итерации для их структуры. Если мы пользуемся одной из предоставленных нам структур, то получаем доступ к уже готовым методам, которые работают в соответствии с этими алгоритмами. Поэтому мы получаем удобный способ выполнения итерации для узлов в K-арном дереве. Также мы несколько улучшаем производительность за счет выполнения меньшего количества операций с DOM.