Bug 1531046 - Quantum Bar highlight should properly support overlapping ranges. r=adw
authorMarco Bonardo <mbonardo@mozilla.com>
Tue, 05 Mar 2019 08:43:04 +0000
changeset 520227 cfc50371b41ce0a24cfc442fced8369f041da287
parent 520226 adc910e55eb67f7d667cdaca586997fca225f492
child 520228 4c9a6871dc033d41fe3da762522ac32e7ae14a66
push id10862
push userffxbld-merge
push dateMon, 11 Mar 2019 13:01:11 +0000
treeherdermozilla-beta@a2e7f5c935da [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersadw
bugs1531046
milestone67.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1531046 - Quantum Bar highlight should properly support overlapping ranges. r=adw Differential Revision: https://phabricator.services.mozilla.com/D21926
browser/components/urlbar/UrlbarUtils.jsm
browser/components/urlbar/tests/unit/test_UrlbarUtils_getTokenMatches.js
browser/components/urlbar/tests/unit/xpcshell.ini
--- a/browser/components/urlbar/UrlbarUtils.jsm
+++ b/browser/components/urlbar/UrlbarUtils.jsm
@@ -13,17 +13,16 @@ var EXPORTED_SYMBOLS = [
   "UrlbarMuxer",
   "UrlbarProvider",
   "UrlbarQueryContext",
   "UrlbarUtils",
 ];
 
 const {XPCOMUtils} = ChromeUtils.import("resource://gre/modules/XPCOMUtils.jsm");
 XPCOMUtils.defineLazyModuleGetters(this, {
-  BinarySearch: "resource://gre/modules/BinarySearch.jsm",
   BrowserUtils: "resource://gre/modules/BrowserUtils.jsm",
   PrivateBrowsingUtils: "resource://gre/modules/PrivateBrowsingUtils.jsm",
   PlacesUIUtils: "resource:///modules/PlacesUIUtils.jsm",
   PlacesUtils: "resource://gre/modules/PlacesUtils.jsm",
   Services: "resource://gre/modules/Services.jsm",
   UrlbarPrefs: "resource:///modules/UrlbarPrefs.jsm",
 });
 
@@ -227,33 +226,42 @@ var UrlbarUtils = {
    *            [matchIndex_0, matchLength_0],
    *            [matchIndex_1, matchLength_1],
    *            ...
    *            [matchIndex_n, matchLength_n]
    *          ].
    *          The array is sorted by match indexes ascending.
    */
   getTokenMatches(tokens, str) {
-    return tokens.reduce((matches, token) => {
-      let index = 0;
+    // To generate non-overlapping ranges, we start from a 0-filled array with
+    // the same length of the string, and use it as a collision marker, setting
+    // 1 where a token matches.
+    let hits = new Array(str.length).fill(0);
+    for (let token of tokens) {
       // Ideally we should never hit the empty token case, but just in case
       // the value check protects us from an infinite loop.
-      while (index >= 0 && token.value) {
-        index = str.indexOf(token.value, index);
+      for (let index = 0, needle = token.value; index >= 0 && needle;) {
+        index = str.indexOf(needle, index);
         if (index >= 0) {
-          let match = [index, token.value.length];
-          let matchesIndex = BinarySearch.insertionIndexOf((a, b) => {
-            return a[0] - b[0];
-          }, matches, match);
-          matches.splice(matchesIndex, 0, match);
-          index += token.value.length;
+          hits.fill(1, index, index + needle.length);
+          index += needle.length;
         }
       }
-      return matches;
-    }, []);
+    }
+    // Starting from the collision array, generate [start, len] tuples
+    // representing the ranges to be highlighted.
+    let ranges = [];
+    for (let index = hits.indexOf(1); index >= 0 && index < hits.length;) {
+      let len = 0;
+      for (let j = index; j < hits.length && hits[j]; ++j, ++len);
+      ranges.push([index, len]);
+      // Move to the next 1.
+      index = hits.indexOf(1, index + len);
+    }
+    return ranges;
   },
 
   /**
    * Extracts an url from a result, if possible.
    * @param {UrlbarResult} result The result to extract from.
    * @returns {object} a {url, postData} object, or null if a url can't be built
    *          from this result.
    */
new file mode 100644
--- /dev/null
+++ b/browser/components/urlbar/tests/unit/test_UrlbarUtils_getTokenMatches.js
@@ -0,0 +1,58 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+/**
+ * Tests UrlbarUtils.getTokenMatches.
+ */
+
+"use strict";
+
+add_task(function test() {
+  const tests = [
+    {
+      tokens: ["mozilla", "is", "i"],
+      phrase: "mozilla is for the Open Web",
+      expected: [[0, 7], [8, 2]],
+    },
+    {
+      tokens: ["mo", "b"],
+      phrase: "mozilla is for the Open Web",
+      expected: [[0, 2], [26, 1]],
+    },
+    {
+      tokens: ["mo", ""],
+      phrase: "mozilla is for the Open Web",
+      expected: [[0, 2]],
+    },
+    {
+      tokens: ["mozilla"],
+      phrase: "mozilla",
+      expected: [[0, 7]],
+    },
+    {
+      tokens: ["mo", "zilla"],
+      phrase: "mozilla",
+      expected: [[0, 7]],
+    },
+    {
+      tokens: ["moz", "zilla"],
+      phrase: "mozilla",
+      expected: [[0, 7]],
+    },
+    {
+      tokens: [""], // Should never happen in practice.
+      phrase: "mozilla",
+      expected: [],
+    },
+    {
+      tokens: ["mo", "om"],
+      phrase: "mozilla mozzarella momo",
+      expected: [[0, 2], [8, 2], [19, 4]],
+    },
+  ];
+  for (let {tokens, phrase, expected} of tests) {
+    tokens = tokens.map(t => ({value: t}));
+    Assert.deepEqual(UrlbarUtils.getTokenMatches(tokens, phrase), expected,
+                     `Match "${tokens.map(t => t.value).join(", ")}" on "${phrase}"`);
+  }
+});
--- a/browser/components/urlbar/tests/unit/xpcshell.ini
+++ b/browser/components/urlbar/tests/unit/xpcshell.ini
@@ -12,8 +12,9 @@ support-files =
 [test_providersManager_maxResults.js]
 [test_tokenizer.js]
 [test_UrlbarController_unit.js]
 [test_UrlbarController_telemetry.js]
 [test_UrlbarController_integration.js]
 [test_UrlbarQueryContext.js]
 [test_UrlbarUtils_addToUrlbarHistory.js]
 [test_UrlbarUtils_getShortcutOrURIAndPostData.js]
+[test_UrlbarUtils_getTokenMatches.js]