HTML5-Beherrschung: Baumdurchquerung

() translation by (you can also view the original English article)

Eines der wichtigsten Konzepte im DOM ist das Durchqueren von Bäumen. Seit sich die Informatik als eigenes Studienfach etabliert hat, wurde jahrzehntelang an Datenstrukturen und Algorithmen geforscht. Eine der am häufigsten verwendeten Strukturen ist ein Baum. Bäume sind überall. Eine sehr rudimentäre, aber nützliche und oft verwendete Version ist ein Binärbaum. Ein Turnier kann als binärer Baum dargestellt werden. Der DOM-Baum ist jedoch nicht binär. Stattdessen ist es ein K-ary-Baum. Jeder Knoten kann null bis N Unterknoten haben, die childNodes genannt werden.

Ein DOM-Baum beherbergt eine Vielzahl möglicher Knotentypen. Es kann unter vielen Text, Element, Comment und andere spezielle wie ProcessingInstruction oder DocumentType geben. Die meisten von ihnen haben per Definition keine childNodes. Sie sind Endpunkte und tragen nur eine einzige Information. Ein Comment-Knoten trägt beispielsweise nur die angegebene Kommentarzeichenfolge. Ein Text-Knoten ist nur zum Speichern einer Inhaltszeichenfolge verfügbar.

Der Element-Knoten hostet andere Knoten. Wir können rekursiv von Element zu Element absteigen, um alle verfügbaren Knoten im System zu durchlaufen.

Ein anschauliches Beispiel

Ein Beispiel, das sich auch auf den vorherigen Artikel zum <template>-Element bezieht, ist das Ausfüllen einer DOM-Teilbaumstruktur. Ein Teilbaum ist ein Teil des Baums, der bei einem bestimmten Element beginnt. Wir nennen das angegebene Element die Unterbaumwurzel. Wenn wir das <html>-Element eines Baums als Unterbaumwurzel nehmen, wäre der Unterbaum fast identisch mit dem echten Baum, der beim document beginnt, also eine Ebene unter dem documentElement.

Das Ausfüllen der Unterbaumstruktur erfordert, dass wir alle Kinder der Unterbaumwurzel durchlaufen. Auf jedem Knoten müssen wir den genauen Knotentyp überprüfen und dann auf die entsprechende Weise fortfahren. Zum Beispiel muss jedes Element wieder als Teilbaumwurzel betrachtet werden. Textknoten hingegen müssen sorgfältiger evaluiert werden. Vielleicht wollen wir auch die Kommentarknoten auf spezielle Direktiven überprüfen. Darüber hinaus sollten auch die Attribute der Elemente berücksichtigt werden.

Für das Szenario verwenden wir eine Methode namens applyModel, um auf Vorlagen basierende Zeichenfolgen mit Werten aus einem Modell zu füllen. Das Verfahren sieht wie folgt aus und könnte natürlich noch weiter optimiert werden. Dennoch ist es für unsere Zwecke sicherlich ausreichend.

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;
}

Sehen wir uns eine Implementierung für das beschriebene Szenario an, die die Methode applyModel bei verschiedenen Gelegenheiten verwendet. Dies erfordert eine Instanz eines template-Elements und ein Objekt namens model, um ein neues DocumentFragment zurückzugeben. Das neue Fragment verwendet die Daten aus dem Modell, um alle Werte von {X} in das Ergebnis der Auswertung des Ausdrucks X mit dem bereitgestellten Objekt zu ändern.

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

	allNodes.forEach(changeNode);
	return fragment;
}

Der vorherige Code verwendet eine Funktion findAllNodes, die einen Knoten nimmt und alle seine Kinder in einem Array speichert. Die Funktion wird dann für jedes Kind rekursiv aufgerufen. Am Ende werden alle Ergebnisse zu einem einzigen Array des gesamten Teilbaums zusammengeführt, d. h. wir transformieren die Baumstruktur in ein 1-dimensionales Array.

Der folgende Codeausschnitt zeigt eine Beispielimplementierung für den beschriebenen Algorithmus.

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;
}

Die Funktion zum Ändern jedes Knotens im Array wird unten gezeigt. Die Funktion führt je nach Art des Knotens einige Manipulationen durch. Wir kümmern uns nur um Attribute und Textknoten.

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;
	}
}

Obwohl der Code leicht zu verstehen ist, ist er nicht sehr schön. Wir haben einige Performance-Probleme, zumal wir viele leider notwendige DOM-Operationen haben. Dies kann mit einem der DOM-Baum-Helfer effizienter durchgeführt werden. Beachten Sie, dass die Methode findAllNodes ein Array mit allen Knoten zurückgibt, nicht nur mit allen Element-Instanzen im Unterbaum. Wenn wir an letzterem interessiert sind, können wir einfach einen querySelectorAll('*')-Aufruf verwenden, der die Iteration für uns durchführt.

Iterieren über Knoten

Eine sofort verfügbare Lösung ist die Verwendung eines NodeIterator. Ein NodeIterator iteriert über Knoten. Es passt fast perfekt zu unseren Kriterien. Wir können einen neuen NodeIterator erstellen, indem wir die createNodeIterator-Methode des document-Objekts verwenden. Es gibt drei entscheidende Parameter:

Der Wurzelknoten des zu iterierenden Unterbaums.
Filter, über welche Knoten ausgewählt / iteriert werden soll.
Ein Objekt mit einem acceptNode für die benutzerdefinierte Filterung.

Während das erste Argument nur ein einfacher DOM-Knoten ist, verwenden die anderen beiden spezielle Konstanten. Sollen beispielsweise alle Knoten angezeigt werden, müssen wir -1 als Filter übergeben. Alternativ können wir NodeFilter.SHOW_ALL verwenden. Wir könnten mehrere Filter auf verschiedene Weise kombinieren. Als Beispiel kann die Kombination der Anzeige aller Kommentare und aller Elemente mit ausgedrückt werden NodeFilter.SHOW_COMMENT | . NodeFilter.SHOW_ELEMENT.

Das dritte Argument ist ein Objekt, das so primitiv aussehen kann wie der folgende Codeausschnitt. Auch wenn das Objekt, das die Funktion umschließt, redundant zu sein scheint, wurde es so angegeben. Einige Browser, z.B. Mozilla Firefox, geben uns die Möglichkeit, das Objekt auf eine einzige Funktion zu reduzieren.

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

Hier akzeptieren wir jeden übergebenen Knoten. Zusätzlich haben wir die Möglichkeit, einen Knoten (und seine Kinder) mit der Option FILTER_REJECT abzulehnen. Wenn wir den Knoten nur überspringen möchten, aber dennoch an seinen untergeordneten Elementen interessiert sind, können wir die Konstante FILTER_SKIP verwenden.

Die Implementierung unseres vorherigen Beispiels mit dem NodeIterator ist ziemlich einfach. Wir erstellen einen neuen Iterator, indem wir die Konstruktormethode im document verwenden. Dann verwenden wir die nextNode-Methode, um über alle Knoten zu iterieren.

Schauen wir uns das transformierte Beispiel an.

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;
}

Die DOM-Suche ist uns vollständig verborgen. Dies ist ein großer Vorteil. Wir fordern nur die gewünschten Knoten an und der Rest wird auf die effizienteste Weise in der Engine des Browsers erledigt. Auf der anderen Seite müssen wir jedoch noch Code zum Iterieren der Attribute bereitstellen.

Obwohl Attribute von der SHOW_ATTRIBUTE-Konstante abgedeckt werden, sind sie nicht als Kinder mit den Elementknoten verbunden. Stattdessen befinden sie sich in einer NamedNodeMap-Sammlung, die vom NodeIterator nicht in die Suche einbezogen wird. Wir können nur über Attribute iterieren, wenn wir die Iteration bei einem Attribut beginnen und uns auf Attribute beschränken.

Das vorherige Beispiel könnte auch die Änderung im bereitgestellten Filter aufrufen. Dies ist jedoch keine gute Vorgehensweise, da wir den Iterator möglicherweise auch für andere Zwecke verwenden möchten. Daher sollte der Iterator eigentlich nur eine schreibgeschützte Lösung präsentieren, die den Baum nicht mutiert.

Auch das Mutieren des Baumes wird vom NodeIterator nicht sehr gut unterstützt. Der Iterator kann man sich wie einen Cursor in einem Dokument vorstellen, der zwischen zwei (dem letzten und dem nächsten) Knoten platziert wird. Daher zeigt ein NodeIterator nicht auf einen beliebigen Knoten.

Den Baum gehen

Wir wollen über Knoten in einem Teilbaum iterieren. Eine andere Möglichkeit, die uns in den Sinn kommt, ist die Verwendung eines TreeWalker. Hier gehen wir den Baum entlang, wie der Name schon sagt. Wir geben einen Wurzelknoten und Elemente an, die in unserer Route berücksichtigt werden sollen, und dann verarbeiten wir. Das Interessante daran ist, dass ein TreeWalker viel mit einem NodeIterator gemeinsam hat. Wir sehen nicht nur bereits viele gemeinsame Eigenschaften, sondern verwendet auch denselben NodeFilter zum Einrichten von Einschränkungen.

In den meisten Szenarien ist der TreeWalker tatsächlich die bessere Wahl als der NodeIterator. Die API des NodeIterator ist für das, was sie liefert, aufgebläht. Der TreeWalker enthält noch mehr Methoden und Einstellungen, verwendet sie aber zumindest.

Der Hauptunterschied zwischen dem TreeWalker und dem NodeIterator besteht darin, dass erstere eine baumorientierte Ansicht der Knoten in einem Teilbaum darstellt und nicht die listenorientierte Ansicht des Iterators. Während der NodeIterator es uns ermöglicht, vorwärts oder rückwärts zu gehen, bietet uns ein TreeWalker auch die Möglichkeit, zum Elternteil eines Knotens, zu einem seiner Kinder oder zu einem Geschwisterknoten zu wechseln.

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;
}

Im Gegensatz zum NodeIterator zeigt der „TreeWalker“ direkt auf einen bestimmten Knoten im Baum. Wenn der Knoten, auf den verwiesen wird, verschoben wird, folgt der TreeWalker daher. Noch wichtiger ist, dass wir effektiv außerhalb des Dokumentbaums landen, wenn der Knoten, auf den verwiesen wird, aus dem Baum entfernt wird. Wenn wir den Ratschlägen für den NodeIterator folgen und den Baum beim Durchlaufen nicht mutieren, werden wir am Ende den gleichen Pfad haben.

Der TreeWalker scheint für unseren Zweck auch fast identisch mit dem NodeIterator zu sein. Es gibt Gründe, warum letztere nicht viel Aufmerksamkeit erlangen konnten. Trotzdem ist der TreeWalker auch nicht sehr bekannt. Vielleicht ist sein Anwendungsbereich einfach zu begrenzt, so dass wir keine Möglichkeit haben, Attribute erneut zu durchlaufen – insbesondere mit der dritten Option, die wir für die DOM-Baum-Iteration haben.

Bereichsauswahl

Schließlich gibt es noch ein drittes Konstrukt, das unter Umständen interessant sein kann. Wenn wir einen Bereich in einem 1-dimensionalen Array auswählen möchten, können wir dies leicht implementieren, indem wir einfach zwei Indizes verwenden: i für die anfängliche(linke) Grenze und f für die letzte (rechte) Grenze, die wir haben, [i, f].

Wenn wir das Array durch eine verkettete Liste ersetzen, können die beiden Indizes auch durch zwei konkrete Knoten [n_i, n_f] ersetzt werden. Der Vorteil dieser Wahl liegt im impliziten Update-Mechanismus. Wenn wir dazwischen Knoten einfügen, müssen wir die Grenzen unseres Bereichs nicht aktualisieren. Auch wenn die linke Grenze aus der verknüpften Liste entfernt wird, erhalten wir einen Bereich, der sich nach links erweitert hat, beispielsweise [0, n_f].

Jetzt haben wir kein 1-dimensionales Problem, sondern eine Baumstruktur. Die Auswahl eines Bereichs eines K-ary-Baums ist nicht so trivial. Wir könnten unseren eigenen Algorithmus entwickeln, aber ein DOM-Baum hat einige spezielle Probleme. Zum Beispiel haben wir Textknoten, die auch Gegenstand eines Bereichs sein können. In unserem DOM-Baum besteht das Sortiment aus vier Eigenschaften. Wir haben einen Startknoten, einen Endknoten und einen Offset für beide.

Es gibt auch Helfer, wie die Methoden selectNode oder selectNodeContents, die die richtigen Aufrufe von setStart und setEnd ausführen. Der Aufruf von selectNodeContents(node) entspricht beispielsweise dem Code-Snippet:

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

Bereiche gehen über die reine programmatische Auswahl hinaus. Sie werden auch für die eigentliche visuelle Auswahl im Browser verwendet. Die Methode getSelection() des window-Kontexts liefert ein Selection-Objekt, das durch Aufrufen von getRangeAt(0) leicht in einen Range umgewandelt werden kann. Wenn nichts ausgewählt ist, schlägt die vorherige Anweisung fehl.

Betrachten wir ein einfaches Beispiel für eine Auswahl, die zu dem folgenden Bild führt.

Hier beginnen wir im Textknoten des ersten Listenelements und enden am Ende des Textknotens eines starken Elements. Das folgende Bild veranschaulicht den abgedeckten Bereich aus Sicht des Quellcodes.

Interessant ist auch die Anzeige des DOM-Baums für die bereitgestellte Range-Instanz. Wir sehen, dass ein solches Spektrum eine ganze Reihe von Knoten abdecken kann, unabhängig von ihren Vorfahren oder Geschwistern.

Durch das Extrahieren der ausgewählten Knoten erhalten wir ein DocumentFragment, das bei einem neuen Listenelement beginnt und nach dem starken Element endet.

Die Extraktion ist eigentlich eine DOM-Mutationsaktion, d. h. sie ändert den vorhandenen Baum. Jetzt bleiben uns die folgenden zwei Punkte, genau wie wir es erwartet hatten.

Da Text Elemente und alles, was darin enthalten sein kann, enthalten kann, muss der Bereich auch diese Fälle abdecken. Auf den ersten Blick ist der Range seltsam konstruiert, da er sich immer um mindestens zwei Fälle kümmern muss: Text und Nicht-Text (meistens Elemente). Wie wir gesehen haben, gibt es jedoch einen guten Grund, diese beiden Fälle zu unterscheiden, da wir sonst keine Textfragmente auswählen könnten.

Dem Range-Objekt fehlen die Iterationsfähigkeiten, die wir zuvor kennengelernt haben. Stattdessen haben wir die Serialisierungs- und Exportfunktionen verbessert. Unser bisheriges Beispiel zu ändern ist daher zunächst umständlich. Dennoch sind wir durch die Einführung einiger neuer Methoden in der Lage, die Flexibilität eines Range mit verbesserter Iteration zu kombinieren.

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;
};

Mit diesen beiden Methoden können wir den Range genau wie die Iteratoren zuvor verwenden. Im Moment können wir nur in eine Richtung gehen; Wir könnten jedoch problemlos Methoden implementieren, um die untergeordneten Elemente zu überspringen, direkt zum übergeordneten Element zu wechseln oder andere Bewegungen auszuführen.

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;
}

Auch wenn Range wie jedes andere JavaScript-Objekt Garbage-Collection ist, empfiehlt es sich dennoch, ihn mit der Funktion detach freizugeben. Einer der Gründe ist, dass alle Range-Instanzen tatsächlich im document gehalten werden, wo sie im Falle von DOM-Mutationen aktualisiert werden.

Es ist von Vorteil, unsere eigenen Iteratormethoden für den Range zu definieren. Die Offsets werden automatisch aktualisiert und wir haben Hilfsmöglichkeiten, wie das Klonen der aktuellen Auswahl als DocumentFragment, das Extrahieren oder Löschen der ausgewählten Knoten. Auch können wir die API für unsere eigenen Bedürfnisse entwerfen.

Abschluss

Das Iterieren durch den DOM-Baum ist ein interessantes Thema für jeden, der über DOM-Manipulation und effizientes Abrufen von Knoten nachdenkt. Für die meisten Anwendungsfälle gibt es bereits eine entsprechende API. Wollen wir eine einfache Iteration? Wollen wir einen Bereich auswählen? Haben wir Lust auf den Baum? Für jede Methode gibt es Vor- und Nachteile. Wenn wir wissen, was wir wollen, können wir die richtige Wahl treffen.

Leider sind Baumstrukturen nicht so einfach wie eindimensionale Arrays. Sie können auf eindimensionale Arrays abgebildet werden, aber die Abbildung folgt demselben Algorithmus wie das Iterieren über ihre Struktur. Wenn wir eine der bereitgestellten Strukturen verwenden, haben wir Zugriff auf Methoden, die diesen Algorithmen bereits folgen. Daher erhalten wir eine bequeme Möglichkeit, einige Iterationen über Knoten in einem K-ary-Baum durchzuführen. Wir sparen auch etwas Leistung, indem wir weniger DOM-Operationen ausführen.