Освоюємо HTML5: обхід дерева

Ukrainian (українська мова) translation by AlexBioJS (you can also view the original English article)

Одна з найважливіших концепцій DOM – обхід дерева (* процес разового відвідування (перевірки та/або відновлення) кожного вузла дерева (структура даних). Тут і надалі примітка перекладача)). Оскільки теорія обчислювальних машин і систем (* комп'ютерні науки; загальна назва для сукупності дисциплін, пов'язаних із конструюванням комп'ютерів та їхнім використанням в обробленні інформації. Об'єднують теоретичні та практичні аспекти багатьох наук, таких як електроніка, програмування, математика, штучний інтелект, людино-машинна взаємодія, конструювання комп'ютерів та ін.) сформувалася як самостійна область досліджень, десятиріччя було витрачено на розроблення структур даних (* спосіб зберігання та організації даних для більш зручного доступу до них та оброблення; може являти собою опис полів опис полів запису, таблиці, списку, масиву, файлу тощо) та алгоритмів (* математична функція чи кінцевий набір описів конкретної послідовності дій (правил), потрібних для того, щоб комп'ютер чи інтелектуальний пристрій виконали за певний час те чи інше завдання, наприклад ущільнення зображення, вибір оптимального маршруту пересилання чи пакета шифрування даних. Алгоритм можна описати блок-схемою. Термін походить від імені давньоперського математика Мухаммеда ібн Муса аль Харезмі, що написав трактат, присвячений алгоритмічному методу). Однією з найчастіше використовуваних структур є дерево. Дерева представлені всюди. Однією з найпростіших і в той же час корисною та часто використовуваною версією дерева є двійкове дерево (* дерево, кожна вершина якого має не більше двох нащадків. Двійкові дерева використовують в алгоритмах сортування і пошуку даних). Спортивне змагання можна представити у вигляді двійкового дерева. Проте дерево DOM не є двійковим. Це K-арне дерево (* дерево з корнем, у кожному вузлі якого є не більше k дочірніх вузлів). Кожний вузол може мати від нуля до N підвузлів, що називаються childNodes.

У дереві DOM міститься велика кількість різноманітних типів вузлів. Це можуть бути Text, Element, Comment та інші додаткові, наприклад ProcessingInstruction або DocumentType окрім багатьох інших. Більшість з них не буде містити яких-небудь childNodes (* дочірніх елементів) за визначенням (* по своїй природі). Крок 1: Макет сторінки у Photoshop

Для початку нам потрібно спланувати наш макет та надати йому крутий вигляд за допомогою Photoshop.

Наочний приклад

Прикладом, що також відноситься до попередньої статті, у якій розглядався елемент <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 повністю прихований від нас. Це дуже вигідно. Ми лише запитуємо потрібні нам вузли, решта виконується найефективнішим способом у движку браузера. Проте, з іншого боку, нам як і раніше потрібно написати код для виконання ітерації для вузлів з атрибутами.

Тепер ми можемо взятися за стильове оформлення. Замість цього вони розташовуються в колекції 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].

Якщо ми замінемо масив зв'язним списком (* список (структура даних), елементи якого не обов'язково розташовано в пам'яті послідовно. Доступ до наступного елемента здійснюють за покажчиком, збереженим у попередньому елементі списку. В останнього елемента покажчик має спеціальне значення, за яким знаходять кінець списку. Список може бути двонапрямленим, коли кожний його елемент містить посилання як на наступний, так і на попередні елементи), то два індекси також можна буде замінити двома конкретними елементами, [n_i, n_f]. Перевага при використанні цього варіанта полягає у прихованому механізмі оновлення. Якщо ми додаємо до діапазону елементи, нам не потрібно оновлювати його границі. Також при видаленні лівої границі зі зв'язного списку ми отримуємо діапазон, що збільшується вліво, на зразок [0, n_f].

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

Також є хелпери, наприклад метод selectNode або selectNodeContents, за допомогою яких виконуються потрібні виклики setStart та setEnd. Наприклад виклик selectNodeContents(node) еквівалентний наступному фрагменту коду:

range.setStart(node, 0);
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 підлягає «збиранню сміття» (* здійснювана під час виконання програми операція видалення непотрібних даних і переупорядкування (об'єднання в більш значні) блоків пам'яті, динамічно розподілювана та необхідна для подальшої роботи. Запускається, коли обсяг вільної пам'яті стає меншим заздалегідь визначеного. Звільнена пам'ять повертається до пулу вільної пам'яті), як і будь-який інший об'єкт JavaScript, як і раніше його видалення за допомогою функції detach вважається усталеною практикою. Одна з причин – те, що всі зразки Range у дійсності зберігаються у document, де вони оновлюються при маніпуляціях з DOM.

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

Завершення

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

На жаль, деревовидні структури не так прості, як одномірні масиви. Їх можна перетворити (* побудувати відповідність) в одномірні масиви, проте при цьому враховуються ті ж самі алгоритми, що й при виконанні ітерації для їх структури. Якщо ми використовуємо одну з наданих структур, то отримуємо доступ до вже готових методів, що працюють згідно з цими алгоритмами. Тому ми отримуємо зручний спосіб виконання ітерації для вузлів у K-арному дереві. Також ми трохи покращуємо продуктивність завдяки виконанню меншої кількості операцій з DOM.