Dominio de HTML5: Traversal de árbol

Spanish (Español) translation by Elías Nicolás (you can also view the original English article)

Uno de los conceptos más importantes en el DOM es el árbol transversal. Desde que la informática se ha establecido como su propio campo de estudio, décadas de investigación se han gastado en estructuras de datos y algoritmos. Una de las estructuras más utilizadas es un árbol. Los árboles están por todas partes. Una versión muy rudimentaria, pero útil y de uso frecuente es un árbol binario. Un torneo puede ser representado como un árbol binario. Sin embargo, el árbol DOM no es binario. En cambio, es un árbol K-ary. Cada nodo puede tener de 0 a N sub-nodos, llamados childNodes

Un árbol DOM alberga una amplia gama de posibles tipos de nodos. Puede haber Text, Element, Comment y otros especiales, como ProcessingInstruction o DocumentType, entre muchos. La mayoría de ellos no tendrán ningún childNodes por definición. Son puntos finales y llevan solamente una sola pieza de información. Por ejemplo, un nodo Comment solo lleva la cadena de comentario especificada. Un nodo Text sólo está disponible para almacenar una cadena de contenido.

El nodo Element aloja otros nodos. Podemos recursivamente descender de elementos a elementos para pasar por todos los nodos disponibles en el sistema.

Un ejemplo ilustrativo

Un ejemplo que también se relaciona con el artículo anterior con respecto al elemento <template> está rellenando una estructura de subárbol DOM. Un subárbol es una parte del árbol, que comienza en un elemento especificado. Llamamos al elemento <html> especificado la raíz del subárbol. Si tomamos el elemento de un árbol como la raíz de subárbol, el subárbol sería casi idéntico al árbol real, que comienza en el document, es decir, un nivel por debajo de documentElement.

Si tomamos el elemento de un árbol como la raíz de subárbol, el subárbol sería casi idéntico al árbol real, que comienza en el documento, es decir, un nivel por debajo de documentElement.Llenar la estructura de subárbol requiere iterar en todos los niños de la raíz del subárbol. En cada nodo necesitamos comprobar el tipo exacto de nodo y luego continuar de la manera apropiada. Por ejemplo, cada elemento debe considerarse como una raíz de subárbol de nuevo. Los nodos de texto, por otro lado, tienen que ser evaluados con más cuidado. Quizás también queramos comprobar los nodos de comentarios para directivas especiales. Además, los atributos de los elementos deben ser considerados también.

Para el escenario usamos un método llamado applyModel para rellenar cadenas templated con valores de un modelo. El método se ve como sigue y podría, por supuesto, ser más optimizado. Sin embargo, para nuestros propósitos es ciertamente suficiente.

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

Veamos una implementación para el escenario descrito, que utiliza el método applyModel en varias ocasiones. Esto toma una instancia de un elemento de template y un objeto llamado model para devolver un nuevo DocumentFragment. El nuevo fragmento utiliza los datos del modelo para cambiar todos los valores de {X} al resultado de evaluar la expresión X usando el objeto proporcionado.

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

	allNodes.forEach(changeNode);
	return fragment;
}

El código anterior utiliza una función findAllNodes, que toma un nodo y almacena todos sus hijos en una matriz. La función se llama entonces recursivamente sobre cada child. Al final, todos los resultados se combinan con una única matriz de todo el subárbol, es decir, transformamos la estructura de árbol en una matriz 1-dimensional.

El fragmento siguiente muestra una implementación de ejemplo para el algoritmo descrito.

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

A continuación se muestra la función para cambiar cada nodo en la matriz. La función realiza algunas manipulaciones dependiendo del tipo de nodo. Sólo nos preocupamos por los atributos y los nodos de texto.

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

Aunque el código es fácil de entender, no es muy bonito. Tenemos bastantes problemas de rendimiento, especialmente porque tenemos muchas operaciones de DOM desafortunadamente necesarias. Esto se puede hacer de manera más eficiente utilizando uno de los ayudantes del árbol DOM. Tenga en cuenta que el método findAllNodes devuelve una matriz con todos los nodos, no sólo todas las instancias Element en el subárbol. Si estamos interesados en este último, simplemente podemos usar una llamada querySelectorAll('*'), que realiza la iteración para nosotros.

Iterando sobre nodos

Una solución que surge inmediatamente es usar un NodeIterator. Un NodeIterator itera sobre los nodos. Se ajusta casi perfectamente a nuestros criterios. Podemos crear un nuevo NodeIterator utilizando el método createNodeIterator del objeto de document. Hay tres parámetros cruciales:

El nodo raíz del subárbol para iterar.
Filtros, que los nodos para seleccionar / iterar más.
Objeto con un acceptNode para filtrado personalizado.

Mientras que el primer argumento es sólo un nodo DOM, los otros dos usan constantes especiales. Por ejemplo, si todos los nodos deben ser mostrados, tenemos que pasar -1 como el filtro. Alternativamente, podemos usar NodeFilter.SHOW_ALL. Podríamos combinar varios filtros de varias maneras. Como ejemplo, la combinación de mostrar todos los comentarios y todos los elementos se puede expresar con NodeFilter.SHOW_COMMENT | NodeFilter.SHOW_ELEMENT.

El tercer argumento es un objeto que puede parecer tan primitivo como el fragmento de código siguiente. Aunque el objeto que envuelve la función parece ser redundante, se ha especificado de esa manera. Algunos navegadores, p. Mozilla Firefox, nos da la posibilidad de reducir el objeto a una sola función.

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

Aquí aceptamos cualquier nodo que se pasa. Además tenemos la opción de rechazar un nodo (y sus hijos) con la opción FILTER_REJECT. Si sólo queremos saltar el nodo, pero todavía estamos interesados en sus hijos, si los hay, podemos usar la constante FILTER_SKIP.

Implementar nuestro ejemplo anterior usando el NodeIterator es bastante sencillo. Creamos un nuevo iterador utilizando el método constructor en el document. Luego usamos el método nextNode para iterar sobre todos los nodos.

Echemos un vistazo al ejemplo transformado.

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

La búsqueda DOM está completamente oculta de nosotros. Este es un gran beneficio. Sólo pedimos los nodos que deseamos, y el resto se hace de la manera más eficiente en el motor del navegador. Sin embargo, en el otro lado todavía tenemos que proporcionar el código para iterating los atributos.

A pesar de que los atributos están cubiertos por la constante SHOW_ATTRIBUTE, no están relacionados con los nodos elemento cuando son children. En su lugar, viven en una colección NamedNodeMap, que no se incluirá en la búsqueda por el NodeIterator. Sólo podemos iterar sobre atributos si comenzamos la iteración en un atributo, limitándonos a solo atributos.

El ejemplo anterior también podría invocar el cambio en el filtro proporcionado. Sin embargo, esto no es una buena práctica, ya que también podríamos usar el iterador para otros propósitos. Por lo tanto, el iterador debe realmente sólo presentar una solución de sólo lectura, que no mutar el árbol.

Muting el árbol también no es muy bien soportado por el NodeIterator. El iterador puede ser pensado como un cursor en un documento, colocándose entre dos (el último y el siguiente) nodo. Por lo tanto, un NodeIterator no apunta a ningún nodo.

Caminando el árbol

Queremos iterar sobre nodos en un subárbol. Otra opción que puede venir a nuestra mente es usar un TreeWalker. Aquí caminamos el árbol como el nombre ya sugiere. Especificamos un nodo raíz y elementos a considerar en nuestra ruta y luego procesamos. La parte interesante es que un TreeWalker tiene mucho en común con un NodeIterator. No solo ya vemos muchas propiedades compartidas, sino que también utiliza el mismo NodeFilter para configurar restricciones.

En la mayoría de los escenarios, TreeWalker es en realidad una mejor opción que NodeIterator. La API del NodeIterator está hinchada por lo que ofrece. TreeWalker contiene aún más métodos y configuraciones, pero al menos las usa.

La principal diferencia entre el TreeWalker y el NodeIterator es que el primero presenta una vista orientada a árbol de los nodos en un subárbol, en lugar de la vista orientada a listas del iterador. Mientras que el NodeIterator nos permite avanzar o retroceder, un TreeWalker nos da también la opción de pasar al padre de un nodo, a uno de sus hijos, o a un hermano.

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

En contraste con el NodeIterator, 'TreeWalker apunta directamente a un nodo específico del árbol. Si el nodo apuntado es movido alrededor, el TreeWalker por lo tanto seguirá. Más importante aún, si el nodo al que se apunta es removido del árbol, entonces efectivamente terminaremos fuera del árbol del documento. Si seguimos el consejo para el NodeIterator y no mutate el árbol durante el recorrido, terminaremos con el mismo camino.

El TreeWalker también parece ser casi idéntico al NodeIterator para nuestro propósito. Hay razones por las que este último no podía ganar mucha atención. No obstante, el TreeWalker tampoco es muy conocido. Tal vez su área de uso es demasiado limitada, lo que nos da la capacidad de recorrer los atributos de nuevo, especialmente con la tercera opción que tenemos para la iteración árbol DOM.

Selección de la rangos

Finalmente, hay un tercer constructo que puede ser interesante bajo ciertas circunstancias. Si queremos seleccionar un rango en una matriz 1-dimensional entonces podemos implementar fácilmente esto usando sólo dos índices: i para el límite inicial (izquierdo) y f para el límite final (derecho) tenemos [i, f] .

Si reemplazamos la matriz con una lista enlazada, los dos índices también pueden ser reemplazados por dos nodos concretos, [n_i, n_f]. La ventaja de esta elección radica en el mecanismo de actualización implícita. Si insertamos nodos entre ellos, no tenemos que actualizar los límites de nuestro rango. Además, si se elimina el límite izquierdo de la lista enlazada, se obtiene un intervalo que se ha expandido a la izquierda, como [0, n_f].

Ahora no tenemos un problema unidimensional, sino una estructura de árbol. Seleccionar un rango de un árbol K-ary no es tan trivial. Podríamos llegar a nuestro propio algoritmo, pero un árbol DOM tiene algunos problemas especiales. Por ejemplo, tenemos nodos de texto, que también pueden estar sujetos a un rango. En nuestro árbol DOM el rango consta de cuatro propiedades. Tenemos un nodo de inicio, un nodo final y un offset para ambos.

También hay ayudantes, como los métodos selectNode o selectNodeContents, que realizan las llamadas correctas de setStart y setEnd. Por ejemplo, invocar selectNodeContents(node) es equivalente al fragmento de código:

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

Los rangos van más allá de la pura selección programática. También se utilizan para la selección visual real en el navegador. El método getSelection() del contexto de ventana window produce un objeto Selection, que puede ser fácilmente transformado en un Range llamando a getRangeAt(0). Si no se selecciona nada, la instrucción anterior falla.

Consideremos un ejemplo sencillo para una selección que da como resultado la siguiente imagen.

Aquí comenzamos en el nodo de texto del primer elemento de lista y terminamos al final del nodo de texto de un elemento fuerte. La siguiente imagen ilustra el rango cubierto desde la perspectiva del código fuente.

También es interesante mostrar el árbol DOM para la instancia de rango Range proporcionada. Vemos que tal rango es capaz de cubrir toda una variedad de nodos independientes de su antepasado o hermano.

Extraer los nodos seleccionados nos da un DocumentFragment, que comienza en un nuevo elemento de lista y termina después del elemento fuerte.

La extracción es en realidad una acción de mutante de DOM, es decir, modificará el árbol existente. Ahora nos quedamos con los dos elementos siguientes, exactamente como esperábamos.

Dado que el texto puede incluir elementos y todo lo contenido en ellos, la gama también necesita cubrir estos casos. A primera vista, Range está extrañamente diseñada, ya que siempre tiene que preocuparse por al menos dos casos: texto y no texto (en su mayoría elementos). Sin embargo, como hemos visto hay una buena razón para distinguir estos dos casos, de lo contrario no podríamos seleccionar fragmentos de texto.

El objeto Range carece de las capacidades de iteración que experimentamos anteriormente. En cambio, hemos mejorado las capacidades de serialización y exportación. Cambiar nuestro ejemplo anterior es, por lo tanto, engorroso al principio. Sin embargo, al introducir algunos nuevos métodos, podemos combinar la flexibilidad de un Range con una iteración mejorada.

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

Estos dos métodos nos permiten utilizar el Range al igual que los iteradores antes. En este momento sólo podemos ir en una dirección; sin embargo, podríamos implementar fácilmente métodos para saltar a los niños, ir directamente al padre o realizar cualquier otro movimiento.

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

A pesar de que el Range se recolecta como cualquier otro objeto JavaScript, sigue siendo una buena práctica liberarlo utilizando la función detach. Una de las razones es que todas las instancias Range se mantienen en el document, donde se actualizan en caso de mutaciones DOM.

Definir nuestros propios métodos iteradores en el rango Range es beneficioso. Los desplazamientos se actualizan automáticamente y tenemos posibilidades auxiliares, como clonar la selección actual como DocumentFragment, extraer o borrar los nodos seleccionados. También podemos diseñar la API para nuestras propias necesidades.

Conclusión

La iteración a través del árbol DOM es un tema interesante para cualquier persona que esté pensando en la manipulación DOM y la recuperación eficiente del nodo. Para la mayoría de los casos de uso ya hay una API correspondiente. ¿Queremos una iteración simple? ¿Queremos seleccionar un rango? ¿Estamos interesados en caminar el árbol? Hay ventajas y desventajas para cada método. Si sabemos lo que queremos, podemos hacer la elección correcta.

Desafortunadamente, las estructuras de árbol no son tan simples como las matrices 1-dimensionales. Pueden ser asignados a matrices 1-dimensionales, pero el mapeo sigue el mismo algoritmo que iterar sobre su estructura. Si utilizamos una de las estructuras proporcionadas, tenemos acceso a métodos que ya siguen estos algoritmos. Por lo tanto, obtenemos una forma conveniente de realizar una iteración sobre nodos en un árbol K-ary. También ahorramos un poco de rendimiento realizando menos operaciones de DOM.