LoginSignup
1
1

More than 3 years have passed since last update.

@piroor(Hiroshi YUKI)

How to sort tabs smartly on Firefox addons and Chromium extensions?

Last updated at Posted at 2019-04-19

この記事の日本語版はこちら

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:

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].

(figure: before and after)

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:

(figure: naive rearrangement of tabs, including 8 times tab moves)

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:

(figure: a quick sort case, including 4 tab moves)

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:

(figure: a quick sort case, including 12 tab moves)

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:

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:

  1. { count: 2, value: [a, b], added: true }
  2. { 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.

(figure: tab moves based on a difference, here are two moves)

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.

(figure: tab moves based on a difference, here are two moves)

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:

  1. { count: 2, value: [a, b], added: true }
  2. { 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.

(figure: tab moves based on two differences, here are four 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:

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.

  1. For example, the Tree Style Tab addon observes tab moves and tries to fix tree structure of tabs automatically based on rearranged tabs. ↩

1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1