Addons for Firefox 57 and later and extensions for Chromium-based browsers (especially Google Chrome) are built on the common API. The tabs.move() method provides ability to move browser's tabs to any position, and addons sorting tabs definitely depend on it. For example:
- Firefox Multi-Account Containers: sorts tabs for each container.
- Sort tabs advanced: sorts tabs with various conditions, like URL.
Then, there is an important topic: how to do that smartly with less API calls and less side effects?
It's not a performance problem of sorting algorithms
A sentence "sort tabs smartly" may remind you sorting algorithms. Yes, it relates to this article, but it is not the subject.
Today JavaScript engines have high performance enough, so the performance of sorting logic itself won't become a critical problem.
However, the performance around sorting of real browser tabs based on the calculated order may be critical. Sorting of too many tabs (some people open 1000 or more tabs) may take much time. Moreover, such tab moves are notified to addons listening tab events and they will trigger side effects1.
Cost to rearrange browser tabs
For example, assume that we want to rearrange tabs from the order [i, h, c, d, e, f, g, b, a, j] to [a, b, c, d, e, f, g, h, i, j].
The difference of before and after is "a", "b", h", and "i": they have been swapped with each other. However, detection of such a "difference" is not easy for programs, so some addons move many tabs naively to sort them in the expected order, like:
The rearrangement algorithm may take n-1 times tab moves on the worst case, and this example case required 8 moves.
The method tabs.move() accepts an array of tab ids as its first parameter, so you may think that there is alternative better solution like:、
browser.tabs.move([a, b, c, d, e, f, g, h, i, j], { index: 0 });
However, such an API call actually produces multiple tab moves for specified tabs internally, like:
browser.tabs.move(a, { index: 0 });
browser.tabs.move(b, { index: 0 + 1 });
browser.tabs.move(c, { index: 0 + 2 });
browser.tabs.move(d, { index: 0 + 3 });
browser.tabs.move(e, { index: 0 + 4 });
browser.tabs.move(f, { index: 0 + 5 });
browser.tabs.move(g, { index: 0 + 6 });
browser.tabs.move(h, { index: 0 + 7 });
browser.tabs.move(i, { index: 0 + 8 });
browser.tabs.move(j, { index: 0 + 9 });
So performance and side effect issues are still there.
Custom sorting with tab moves
Previous example is based on a strategy: sort an array of tab objects with Array.prototype.sort() and rearrange real browser tabs to match to the sorted result. Then there is another way: how about custom sorting including real tab moves?
Here is an example of a quick sort implementation including injected tabs.move():
// A quick sort based on recursive function calls.
function quickSort(tabIds, startIndex, endIndex) {
const pivot = tabIds[Math.floor((startIndex + endIndex) / 2)];
let left = startIndex;
let right = endIndex;
while (true) {
while (tabIds[left] < pivot) {
left++;
}
while (pivot < tabIds[right]) {
right--;
}
if (right <= left)
break;
// Move real tabs together with sorted array elements.
browser.tabs.move(tabIds[left], { index: right });
browser.tabs.move(tabIds[right], { index: left });
const tmp = tabIds[left];
tabIds[left] = tabIds[right];
tabIds[right] = tmp;
left++;
right--;
}
if (startIndex < left - 1) {
quickSort(tabIds, startIndex, left - 1);
}
if (right + 1 < endIndex ){
quickSort(tabIds, right + 1, endIndex);
}
}
const tabs = await browser.tabs.query({windowId: 1 });
quickSort(tabs.map(tab => tab.id), 0, tabIds.length - 1);
A rearranging from [i, h, c, d, e, f, g, b, a, j] to [a, b, c, d, e, f, g, h, i, j] will be produced as:
Yes, this rearranging is completed with just 4 tab moves. The number of steps is a half of the initial example, so this looks better than it.
But it is a hasty judgment. This is just one of best cases on the quick sort algorithm, the original order [i, h, c, d, e, f, g, b, a, j] just contains swapped "a", "b", "h" and "i" near its edges. If swapped elements are placed near the center like [c, d, i, h, e, b, a, f, g, j], the algorithm takes more cost:
This case takes 12 moves. The quick sort algorithm may move an element multiple times in worse cases and take more cost larger than the naive algorithm.
(And there is one more demerit: it is one of unstable sorting algorithms. For example the Firefox Multi-Account Containers tries to sort tabs for each container, so if it sorts tabs based on the quick sort, tabs of each container may be scrambled on each sorting.)
Is there any better approach which universally works well with less steps?
Application of the algorithm of "diff"
Concepts of the diff or the Levenshtein distance may become a solution of this topic.
The "diff" is one of classic programs on Unix like environments, represents differences of two sources. You might to use it as the git diff command to show your local changes. For example, if there are two sources A = [a, b, c, d] and B = [a, c, d, b], differences of them may be reported as:
a
- b
c
d
+ b
Lines starting with - mean deletions (appears only on the A), + mean additions (appears only on the B). Rest parts are common in both sources. The example above means that you can make A to B only with one move: moving "b" from 2 to 4. "The algorithm of diff" means a logic to calculate such a smallest steps of editing.
This means that you can rearrange tabs with smallest steps with differences calculated from two sources: current order of tabs and expected order of tabs.
Diff implementations in JavaScript
The diff is implemented in various languages, including JavaScript. Here is examples of JS-based diff:
-
jsdiff: the
diffnpm package. (3 Clauses BSD license) - diff.js contained in the Tree Style Tab addon: a ported version of a diff implementation in Python. (Python Software Foundation License)
You can use such libraries to rearrange tabs smartly, and there are some hints to choose a library:
- Is its license compatible to the one of your product?
- Is its internal format available as an output?
- Are array sources acceptable?
For example, the jsdiff (diff module of npm) returns calculated differences in a format like following:
[
{ count: 1, value: [a] }, // common
{ count: 1, value: [b], removed: true }, // deletion
{ count: 2, value: [c, d] }, // common
{ count: 1, value: [b], added: true } // addition
]
Such a format is useful to rearrange tabs. And, array of tab ids is also useful to compare orders of tabs. So an implementation which supports such type I/O will matches to this purpose. The jsdiff (npm's diff) looks good on these viewpoints.
Rearranging of tabs based on differences
Three arrays are required to rearrange tabs with calculated differences: the "original order", the "destination order", and the "current order while rearranging".
const tabs = await borwser.tabs.query({ currentWindow: true });
const beforeIds = tabs.map(tab => tab.id); // the "original order"
const afterIds = tabs.sort(comparator)
.map(tab => tab.id); // the "destination order"
let currentIds = beforeIds.slice(0); // the "current order", initiated with the original order
Let's calculate differences from "original" and "destination" orders, and move browser tabs based on that.
const differences = diff.diffArrays(beforeIds, afterIds);
for (const difference of differences) {
if (!difference.added) // ignore "deletion" and "common".
continue;
// Put codes to move tabs here.
}
Only "addition" differences need to be operated. In other words, not only "common" but "deletion" should be ignored also, because tabs are moved based on corresponding "addition" differences.
For a new "addition" difference, you need to calculate the destination index for the moved tabs. It is used as a parameter for tabs.move().
// Here are operations to move tabs inside the "for" loop.
// There are one ore more moving tabs for an addition.
const movingIds = difference.value;
// Get the rightmost moving tab.
const lastMovingId = movingIds[movingIds.length - 1];
// Get the index of the tab next to the destination position.
const nearestFollowingIndex = afterIds.indexOf(lastMovingId) + 1;
// If tabs aren't moved to the last position, the destination
// index is same to the one of the tab next to the destination
// position, in the "current order".
let newIndex = nearestFollowingIndex < afterIds.length ? currentIds.indexOf(afterIds[nearestFollowingIndex]) : -1;
if (newIndex < 0)
newIndex = beforeIds.length;
// Get the current index of the leftmost moving tab.
const oldIndex = currentIds.indexOf(movingIds[0]);
// if you are going to move tabs to right, the destination index
// must be shifted to left.
if (oldIndex < newIndex)
newIndex--;
Now tabs are ready to be moved via the tabs.move() method. It accepts an array of ids as its first parameter, so you should do that to reduce needless API call.
// Move real browser tabs.
browser.tabs.move(movingIds, {
index: newIndex
});
// Synchronize the "current order" array to the real order of
// tabs modified via the API call.
currentIds= currentIds.filter(id => !movingIds.includes(id));
currentIds.splice(newIndex, 0, ...movingIds);
Real browser tabs are moved asynchronously after the API is called, but you should run all tab moves synchronously in an event loop, to avoid unexpected tab moves from external factors. So you should not use await for this API call.
And please remind that you need to calculate the index parameter based on the "current order" updated with the previous API call, instead of the "original order" and the "destination order". This is the reason why these sample codes don't touch to any index property of tab objects.
Let's visualize what's happen while rearranging. Assume that you are going to rearrange [i, h, c, d, e, f, g, b, a, j] tabs to [a, b, c, d, e, f, g, h, i, j] - this is same to the first example. The initial state is:
-
beforeIds: [i, h, c, d, e, f, g, b, a, j] -
afterIds: [a, b, c, d, e, f, g, h, i, j] -
currentIds: [i, h, c, d, e, f, g, b, a, j] - real browser tabs: [i, h, c, d, e, f, g, b, a, j]
The calculated differences of beforeIds and afterIds is:
// Note that actual "value" contains integer values (tab's id).
// For readability I use alphabets here.
[
{ count: 2, value: [i, h], removed: true },
{ count: 2, value: [a, b], added: true },
{ count: 5, value: [c, d, e, f, g] },
{ count: 2, value: [b, a], removed: true },
{ count: 2, value: [h, i], added: true },
{ count: 1, value: [j] }
]
As I described before, only these two "addition" differences should be operated:
{ count: 2, value: [a, b], added: true }{ count: 2, value: [h, i], added: true }
Let's move "a" and "b" based on the first "addition". The destination index is calculated based on the tab next to the rightmost adding tab (= "b"), in the "current order". it is the index of "c" in the currentIds, thus it's 2.
Please pay attention: they are rearranged from "b, a" to "a, b", on the sidelines of the operation. After that the currentIds is also updated to [i, h, a, b, c, d, e, f, g, j] to synchronize to the real browser tabs.
And, let's move "h" and "i" based on the second "addition". The destination index is calculated based on the tab next to the rightmost adding tab (= "i"), in the "current order". it is the index of "j" in the currentIds, thus it's 9. And, it must be shifted to 8 because these tabs are going to be moved to right.
Please pay attention, they are rearranged from "i, h" to "h, i". After that the currentIds is also updated to [a, b, c, d, e, f, g, h, i, j] with a synchronization.
Finally this rearranging took only 2 API calls and 4 moves - the cost became a half of the one of the naive algorithm.
How about a worse case on the quick sort: rearranging from the order [c, d, i, h, e, b, a, f, g, j] ? The calculated differences is:
[
{ count: 2, value: [a, b], added: true },
{ count: 2, value: [c, d] },
{ count: 2, value: [i, h], removed: true },
{ count: 2, value: [e] },
{ count: 2, value: [b, a], removed: true },
{ count: 2, value: [f, g] },
{ count: 2, value: [h, i], added: true },
{ count: 1, value: [j] }
]
Extracted "addition" differences are:
{ count: 2, value: [a, b], added: true }{ count: 2, value: [h, i], added: true }
They are quite same to the previous example, so this will also take 2 API calls and 4 moves.
Conclusion
These results mean that rearranging of tabs based on the algorithm of diff is stably efficient. It is reasonable to reduce real tab moves with this approach, because calculation of differences in pure JavaScript is fast enough.
I've already created pull requests for some addons to introduce this improvement:
- Sort tabs with less steps by piroor · Pull Request #1377 · mozilla/multi-account-containers
- Sort tabs with less steps by piroor · Pull Request #2 · monomon/sort-tabs-advanced
This article and these PRs are based on the tab rearranging operation in the Tree Style Tab addon which was introduced to synchronize the order of internal tab data to real browser tabs. It uses another diff implementation, but the logic is same to the one described at this article, because the format of calculated differences is similar to npm's diff.
Such an optimization is known as one of important strategies of the "virtual DOM" architecture, known as a part of the React framework. If your product has some bottlenecks around too frequently executed APIs, let's try to optimize with this approach.
-
For example, the Tree Style Tab addon observes tab moves and tries to fix tree structure of tabs automatically based on rearranged tabs. ↩