src/vs/editor/common/model/bracketPairsTextModelPart/bracketPairsTree/concat23Trees.ts/concat23Trees
export function concat23Trees(items: AstNode[]): AstNode | null {
	if (items.length === 0) {
		return null;
	}
	if (items.length === 1) {
		return items[0];
	}

	let i = 0;
	/**
	 * Reads nodes of same height and concatenates them to a single node.
	*/
	function readNode(): AstNode | null {
		if (i >= items.length) {
			return null;
		}
		const start = i;
		const height = items[start].listHeight;

		i++;
		while (i < items.length && items[i].listHeight === height) {
			i++;
		}

		if (i - start >= 2) {
			return concat23TreesOfSameHeight(start === 0 && i === items.length ? items : items.slice(start, i), false);
		} else {
			return items[start];
		}
	}

	// The items might not have the same height.
	// We merge all items by using a binary concat operator.
	let first = readNode()!; // There must be a first item
	let second = readNode();
	if (!second) {
		return first;
	}

	for (let item = readNode(); item; item = readNode()) {
		// Prefer concatenating smaller trees, as the runtime of concat depends on the tree height.
		if (heightDiff(first, second) <= heightDiff(second, item)) {
			first = concat(first, second);
			second = item;
		} else {
			second = concat(second, item);
		}
	}

	const result = concat(first, second);
	return result;
}