Làm chủ HTML5: Tree Traversal (Duyệt Cây)

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

Một trong những khái niệm quan trọng nhất trong DOM là tree traversal (duyệt cây). Từ khi khoa học máy tính đã được thiết lập như là lĩnh vực nghiên cứu của riêng của nó, hàng thập kỷ nghiên cứu đã dành cho các cấu trúc dữ liệu và các thuật toán. Một trong những cấu trúc được sử dụng nhiều nhất là tree. Tree ở khắp nơi. Một phiên bản rất thô sơ, nhưng hữu ích và thường được sử dụng là binary tree (cây nhị phân). Giải đấu có thể được biểu diễn dưới dạng một binary tree. Tuy nhiên DOM tree không phải là nhị phân. Thay vào đó nó là một K-ary tree. Mỗi node (nút) có thể có số từ zero đến N sub-node (nút con), được gọi là childNodes.

Cây DOM chứa nhiều loại nút có thể có. Có thể có Text, Element, Comment và các đặc biệt khác, chẳng hạn như ProcessingInstruction hoặc DocumentType, trong số nhiều. Hầu hết chúng sẽ không có childNodes theo định nghĩa. Họ là những điểm kết thúc và chỉ mang theo một thông tin duy nhất. Chẳng hạn, node Comment chỉ mang chuỗi comment cụ thể. Node Text chỉ có sẵn để lưu trữ một chuỗi nội dung.

Node Element nhóm những node khác. Chúng ta có thể hạ đệ quy qua từng phần tử để đi xuyên suốt cảc node trong hệ thống.

Ví dụ minh hoạ

Một ví dụ cũng liên quan đến bài viết trước về thành phần <template> là việc thêm vào một cấu trúc subtree của DOM. Một subtree là một phần của tree, nó bắt đầu từ một phần tử cụ thể. Chúng tôi gọi những phần tử đặc trung này là gốc subtree. Nếu chúng ta xem phần tử <html> của một tree là gốc subtree, thì subtree gần như là một tree thực thụ, nó bắt đầu với document, một cấp bên dưới documentElement.

Bổ sung vào cấu trúc subtree cần chúng ta lặp lại tất cả các con của gốc subtree. Trên mỗi node, chúng ta cần kiểm tra kiểu chính xác của node và sau đó đi theo hướng thích hợp. Ví dụ mỗi phần tử cần xem xét như là một gốc subtree. Text node, theo cách khác phải được đánh giá cẩn thận hơn. Có lẽ chúng ta cũng muốn kiểm tra các node của bình luận cho các directive đặc biệt. Hơn thế nữa, các thuộc tính của các thành phần cũng nên được lưu tâm hơn.

Trong tình huống chúng ta sử dụng một phương thức applyModel để bổ sung vào những chuỗi định dạng với các giá trị từ một model. Phương thức này trông như sau và dĩ nhiên có thể tối ưu sau đó. Tuy nhiên, nó vẫn đủ cho mục đích của chúng ta.

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

Hãy xem một triển khai cho kịch bản được mô tả, sử dụng phương thức applyModel vào những dịp khác nhau. Nó sẽ lấy một giá trị của một template và một đối tượng là model để trả về một DocumentFragement mới.eeeeeee Phân khúc mới dùng data từ một model để thay đổi tất cả giá trị từ {X} đến kết quả của việc đánh giá biểu thức X sử dụng đối tượng được cung cấp.

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

	allNodes.forEach(changeNode);
	return fragment;
}

Code trước đây dùng một hàm findAllNodes, hàm này lấy một node và lưu tất cả con của nó vào một mảng. Hàm được gọi đệ quy trên mỗi node con. Cuối cùng tất cả kết quả được nhập vào thành một mảng của cả subtree, ví dụ chúng ta chủng cấu trúc tree sang mảng một chiều.

Đoạn code sau đây hiển thị một ví dụ triển khai cho thuật toán được mô tả:

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

Hàm này để thay đổi mỗi node trong mảng được hiển thị bên dưới. Hàm thực hiện vài xử lý tuỳ vào hình thức của node. Chúng ta chỉ quan tâm về các thuộc tính và text node.

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

Mặc dù đoạn code rất dễ hiểu, nhưng không phải rất tốt. Chúng ta có khá nhiều vấn đề về hiệu năng, đặc biệt khi có rất nhiều xử lý DOM không cần thiết. Điều này có thể được thực hiện hiệu quả hơn bằng cách sử dụng một trong những tree helper của DOM. Lưu ý rằng phương thức findAllNodes trả về một mảng với tất cả các node, không chỉ tất cả các giá trị của Element trong cây con. Nếu chúng ta thú vị với phần sau đó, đơn giản chúng ta có thể dùng querySelectorAll('*'), để thực hiện việc chạy vòng lặp cho chúng ta.

Chạy vòng lặp quá các node

Một giải pháp lập tức ra đời là sử dụng một NodeIterator. Một NodeIterator sẽ lặp qua các node. Nó hoàn toàn phụ hợp với tiêu chuẩn của chúng ta. Chúng ta có thể tạo một NodeIterator mới bằng việc dùng phương thức NodeIterator của đối tượng document. Có ba tham số chủ yếu:

Node gốc của subtree cần chạy vòng lặp.
Bộ lọc, những node được chọn và chạy vòng lặp.
Một đối tượng với một acceptNode cho việc lọc dữ liệu tuỳ chọn.

Trong khi tham số đầu tiên thuần tuý chỉ là một DOM node, hai tham số còn lại là các hằng số đặc biệt. Ví dụ, nếu tất cả các nodes được hiển thị, chúng ta phải truyền -1 như bộ lọc. Thay vì vậy chúng ta có thể dùng NodeFilter.SHOW_ALL. Chúng ta có thể kết hợp nhiều bộ lọc theo nhiều cách. Ví dụ, sự kết hợp của việc hiển thị tất cả bình luận và tất cả thành phần có thể biểu hiện với NodeFilter.SHOW_COMMENT | NodeFilter.SHOW_ELEMENT.

Tham số thứ ba là một đối tượng trông nguyên thuỷ như đoạn code sau đây. Thậm chí đối tượng bao hàm chức năng trông dư thừa, thì nó cũng đặc xác định theo cách đó. Vài trình duyệt, như Mozilla Firefox cho chúng ta khả năng giảm đối tượng xuống một hàm đơn lẻ.

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

Ở đây chúng ta chấp nhận bất kỳ node nào được truyền vào. Thêm vào đó chúng ta có chọn lựa để từ chối một node (và con của nó) với chọn lựa FILTER_REJECT. Nếu chúng ta chỉ muốn bỏ qua node, nhưng vẫn hứng thú với các con của nó, nếu có thì bạn có thể dùng hằng số FILTER_SKIP.

Việc triển khai ví dụ trước đó với NodeIterator khá là trực tiếp. Chúng ta tạo một vòng lặp mới bằng việc dùng phương thức constructor trong document. Sau đó chúng ta dùng nextNode để lặp lại qua các node.

Hãy nhìn xem ví dụ đã chuyển đổi.

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

Việc tra cứu DOM hoàn toàn được ẩn giấu. Đây là một lợi ích tuyệt vời. Chúng ta chỉ yêu cầu node chúng ta muốn, và phần còn lại được thực hiện theo cách hiệu quả nhất trong cơ chế của trình duyệt. Tuy nhiên, ở mặt khác chúng ta vẫn phải cung cấp code để lọc các thuộc tính.

Thậm chí các thuộc tính được đề cập bởi hằng số SHOW_ATTRIBUTE, chúng không phải là con của những thành phần node. Thay vào đó chúng tồn tại trong NameNodeMap, sẽ không được bao gồm trong việc tra cứu bởi NodeIterator. Chúng ta chỉ có thể lặp lại qua các thuộc tính nếu chúng ta bắt đầu vòng lặp ở một thuộc tính, giới hạn bản thân chỉ ở những thuộc tính.

Ví dụ trước đó cũng kích thích thay đổi trong bộ lọc đã được cung cấp. Tuy nhiên là không phải một thực hành tốt, cũng như chúng ta có thể muốn dùng vòng lặp cho những mục đích khác. Do đó iterator nên thật sự hiện diện như một giải pháp đọc thôi, không phải để biến đổi tree.

Việc biến đổi tree cũng không được hỗ trợ tốt từ NodeIterator. Vòng lặp có thể xem như một con trỏ trong một tài liệu, được đặt giữa hai node (node trước đó và kế tiếp). Do đó, một NodeIterator không chỉ đến bất kỳ node nào.

Di chuyển trong tree

Chúng ta muốn lặp lại qua các node trong một subtree. Một chọn lựa có thể xuất hiện trong tâm trí của bạn là dùng một TreeWalker. Ở đây chúng ta di chuyển trong tree như tên gọi. Chúng ta xác định node gốc và các thành phần để xem xét đường đi và sau đó tiến hành xử lý. Phần thú vị là một TreeWalker có rất nhiều tương đồng với NodeIterator. Không chỉ chúng đã thấy nhiều thuộc tính được chia sẻ, nó cũng dùng cùng NodeFilter để thiết lập các quy tắc.

Trong đa số tình huống TreeWalker thực sự là chọn lựa tốt hơn NodeIterator. API của NodeIterator được cho là cồng kềnh hơn những gì nó mang lại. TreeWalker thậm chí có nhiều phương thức và thiết lập, nhưng ít nhất dùng chúng.

Sự khác nhau giữa TreeWalker và NodeIterator là TreeWalker đại diện cho view theo hướng tree của các node trong một subtree, thay vì view dựa theo hướng list (danh sách). Khi NodeIterator cho phép chúng ta di chuyển tới hoặc lùi, một TreeWalker mang đến chọn lựa di chuyển đến cấp cha của một node, đến một trong cấp con của nó, hoặc đến đồng cấp anh em của nó.

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

Trái ngược với NodeIterator, TreeWalker trực tiếp đi đến một node cụ thể trong tree. Nếu node được trỏ đến đã được chuyển đi, TreeWalker sẽ đi theo. Quan trọng hơn, nếu node được chỉ đến bị gỡ bỏ khỏi tree, thì chúng ta sẽ kết thúc một cách hiệu quả ở ngoài document tree. Nếu ta tuân thủ lời khuyên cho NodeIterator và không biến đổi tree suốt quá trình di chuyển, chúng ta sẽ nhận được cùng đường di chuyển.

TreeWalker dường như cũng gần như NodeIterator cho mục đích của chúng ta. Có nhiều lý do NodeIterator không được chú ý nhiều. Tuy nhiên TreeWalker cũng không phải quá nổi tiếng. Có lẽ phạm vi sử dụng của nó quá hạn chế, cho chúng tôi không có khả năng đi qua các thuộc tính một lần nữa - đặc biệt là với tùy chọn thứ ba chúng ta có cho việc lặp lại DOM tree.

Chọn lựa phạm vi

Cuối cùng, có một cấu trúc thứ ba có thể khá thú vị trong những trường hợp nhất định. Nếu chúng ta muốn chọn một range trong một mảng 1 chiều thì chúng ta có thể dễ dàng thực hiện bằng cách chỉ sử dụng hai index (chỉ mục): i cho biên độ trái và f cho biên độ trái, [i, f]

Nếu chúng ta thay thế mảng với một linked list (danh sách liên kết) sau đó hai index cũng có thể được thay thế với 2 node thực sự, [n_i, n_f]. Lợi điểm của chọn lựa này dựa trên cơ chế cập nhật. Nếu chúng ta chèn node vào giữa hai node này, chúng ta không phải cập nhật biên độ cho phạm vi. Nếu biên độ trái bị bỏ ra khỏi danh sách liên kết, thì chúng ta có một range được mở rộng về phía trái, chẳng hạn [0, n_f]

Bây giờ chúng tôi không có một vấn đề 1 chiều, mà là của cấu trúc tree. Chọn một range của tree K-ary không phải dễ dàng. Chúng ta có thể đưa ra thuật toán của riêng mình, nhưng một DOM tree có một số vấn đề đặc biệt. Ví dụ, chúng ta có những text node, chúng có thể là subject cho một range. Trong DOM Tree của chúng ta, range gồm có 4 thuộc tính. Chúng ta có một node khởi đầu, một node kết thúc và một offset cho cả hai.

Cũng có những helper, như phương thức selectNode hoặc selectNodeContents, chúng thực hiện việc gọi setStart và setEnd. Ví dụ, việc kích hoạt selectNodeContents(node) tương đương với đoạn code:

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

Các phạm vi vượt xa sự lựa chọn thuần tuý của chương trình. Chúng cũng được sử dụng để lựa chọn trực quan thực sự trong trình duyệt. Phương thức getSelection() của window mang đến đối tượng Selection, có thể dễ dàng được chuyển đổi đến một Range bằng việc gọi getRangeAt(0). Nếu không có gì được chọn, phần trình bày trước đó sẽ không có.

Hãy xem xét một ví dụ đơn giản cho một chọn lựa cho ra kết quả như hình bên dưới.

Ở đây chúng ta bắt đầu với text node của mục đầu tiên trong list và kết thúc vào mục cuối cùng của text node của một thành phần strong. Hình dưới đây minh hoạ phạm vị đã được chỉ ra từ góc nhìn vào mã nguồn.

Việc hiển thị DOM tree cho giá trị Range đã cung cấp cũng thú vị. Chúng ta thấy rằng phạm vi như vậy có thể bao gồm một loạt các node độc lập với các node nguồn gốc của nó hay các họ hàng của chúng.

Việc trích xuất các node đã chọn cho ta một DocumentFragment, nó bắt đầu với một danh sách item mới và kết thúc với thành phần

Khai thác này thực sự là một hành động làm biến đổi DOM, tức là nó sẽ sửa đổi tree hiện có. Bây giờ chúng tôi còn lại hai mục sau đây, chính xác như chúng tôi mong đợi.

Khi text có thể bao gồm các thành phần và mọi thứ bên trong chúng, khoảng cách cũng cần được đề cập những trường hợp này. Thoạt nhìn, Range được thiết kế kỳ lạ, vì nó luôn cần phải quan tâm đến ít nhất hai trường hợp: văn bản và không phải văn bản (chủ yếu là các phần tử). Tuy nhiên, như chúng ta đã thấy có lý do đúng cho việc phận biệt hai tình huống này, nếu không chúng ta không thể chọn lựa các phân đoạn văn bản.

Đối tượng Range không có khả năng lặp lại mà chúng ta đã trải nghiệm trước đó. Thay vào đó, chúng tôi đã cải tiến khả năng serialization (định dạng dữ liệu cho lưu trữ) và export (xuất dữ liệu) Do đó việc thay đổi ví dụ trước đây của chúng tôi vào lần đầu trở nên nhọc nhằn. Tuy nhiên, bằng cách giới thiệu một vài phương pháp mới, chúng ta có thể kết hợp sự linh hoạt của một Range với sự lặp lại đã cải thiện.

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

Hai phương thức này cho phép chúng ta dùng Range giống như những iterator trước. Bây giờ chúng ta chỉ có thể đi vào một chiều; tuy nhiên chúng ta có thể dễ dàng triển khai những phương thức để bỏ qua các node con, đi đến thẳng node cha hoặc thực hiện bất kỳ di chuyển khác.

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

Thậm chí dù Range là garbage collected (tự đông được dọn dẹp khi không cần dùng) như những đối tượng khác của JavaScript, thì vẫn là thực tiễn tốt khi giải phóng nó với hàm detach. Một trong những lý do là tất cả giá trị Range thực sự được giữ trong document, ở đây chúng được cập nhật trong trường hợp DOM mutation (thay đổi).

Định nghịa những phương thức iterator trong Range rất có lợi. Offset được tự động câp nhật và chúng ta có các khả năng nhưng sao chép chọn lựa hiện thời như một DocumentFragment, trích xuất hoặc xoá những node đã chọn. Chúng ta cũng thiết kế API cho nhu cầu riêng của chúng ta.

Tổng kết

Chạy vòng lặp qua DOM tree là một chủ đề thú vị cho bất kỳ ai đang nghĩ đến việc xử lý DOM và cách lấy node hiệu quả. Hầu hết những trường hợp đều đã có một API tương ứng. Liệu chúng ta có muốn một vòng lặp thuần tuý? Chúng ta có muốn chọn một phạm vi? Chúng ta có quan tâm đến việc đi qua tree? Có những ưu thế và bất lợi ở từng phương pháp. Nếu chúng ta biết chúng ta muốn gì, chúng ta có thể chọn lựa đúng.

Thật không may, các cấu trúc cây không đơn giản như các mảng 1 chiều. Chúng có thể được ánh xạ thành các mảng 1 chiều nhưng việc ánh xạ dữ liệu theo cùng một thuật toán tương tự như việc lặp lại cấu trúc của nó. Nếu chúng ta sử dụng một trong các cấu trúc được cung cấp, chúng ta truy xuất vào các phương pháp đã tuân theo các thuật toán này. Do đó chúng ta có một cách thuận tiện để thực hiện một số vòng lặp qua các node trong tree K-ary. Chúng ta tăng hiệu suất bằng cách thực hiện ít việc xử lý DOM.