Bug 1073967 - Storage Inspector columns should use natural sort r=nchevobbe
authorMichael Ratcliffe <mratcliffe@mozilla.com>
Mon, 10 Apr 2017 18:04:25 +0100
changeset 354362 ef0ad7316ebb979325048663ffcd297715169301
parent 354361 3568513947d2a5a675ee8071d8d9f591f4d4db1c
child 354363 ad0ce16193f50abfacae7aeb3cfd5786461e9b46
push id41266
push usermratcliffe@mozilla.com
push dateFri, 21 Apr 2017 21:21:53 +0000
treeherderautoland@ef0ad7316ebb [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersnchevobbe
bugs1073967
milestone55.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 1073967 - Storage Inspector columns should use natural sort r=nchevobbe Changlist: - Added Jim Palmer's well proven natural sort algorithm. - Added natural sort license (MIT). - Use natural sort everywhere inside TableWidget.js wherever we use .sort() - Changed browser_storage_overflow.js so that the test is faster and more maintainable. The test now also tests column sorting (ascending and descending). - Use natural sort everywhere inside storage.js wherever we need to slice the array. Without natural sort here we get e.g. row-1, row-10, row-100, row-2 etc. MozReview-Commit-ID: FUY7pcLIYml
devtools/client/shared/moz.build
devtools/client/shared/natural-sort.js
devtools/client/shared/widgets/TableWidget.js
devtools/client/storage/test/browser_storage_overflow.js
devtools/client/storage/test/head.js
devtools/client/storage/test/storage-overflow.html
devtools/server/actors/storage.js
toolkit/content/license.html
--- a/devtools/client/shared/moz.build
+++ b/devtools/client/shared/moz.build
@@ -33,16 +33,17 @@ DevToolsModules(
     'file-saver.js',
     'file-watcher-worker.js',
     'file-watcher.js',
     'getjson.js',
     'inplace-editor.js',
     'Jsbeautify.jsm',
     'key-shortcuts.js',
     'keycodes.js',
+    'natural-sort.js',
     'network-throttling-profiles.js',
     'node-attribute-parser.js',
     'options-view.js',
     'output-parser.js',
     'poller.js',
     'prefs.js',
     'react-utils.js',
     'scroll.js',
new file mode 100644
--- /dev/null
+++ b/devtools/client/shared/natural-sort.js
@@ -0,0 +1,106 @@
+/*
+ * Natural Sort algorithm for Javascript - Version 0.8.1 - Released under MIT license
+ * Author: Jim Palmer (based on chunking idea from Dave Koelle)
+ *
+ * Includes pull request to move regexes out of main function for performance
+ * increases.
+ *
+ * Repository:
+ *   https://github.com/overset/javascript-natural-sort/
+ */
+
+"use strict";
+
+var re = /(^([+\-]?\d+(?:\.\d*)?(?:[eE][+\-]?\d+)?(?=\D|\s|$))|^0x[\da-fA-F]+$|\d+)/g;
+var sre = /^\s+|\s+$/g;   // trim pre-post whitespace
+var snre = /\s+/g;        // normalize all whitespace to single ' ' character
+
+// eslint-disable-next-line
+var dre = /(^([\w ]+,?[\w ]+)?[\w ]+,?[\w ]+\d+:\d+(:\d+)?[\w ]?|^\d{1,4}[\/\-]\d{1,4}[\/\-]\d{1,4}|^\w+, \w+ \d+, \d{4})/;
+var hre = /^0x[0-9a-f]+$/i;
+var ore = /^0/;
+var b0re = /^\0/;
+var e0re = /\0$/;
+
+exports.naturalSortCaseSensitive =
+function naturalSortCaseSensitive(a, b) {
+  return naturalSort(a, b, false);
+};
+
+exports.naturalSortCaseInsensitive =
+function naturalSortCaseInsensitive(a, b) {
+  return naturalSort(a, b, true);
+};
+
+/**
+ * Sort numbers, strings, IP Addresses, Dates, Filenames, version numbers etc.
+ * "the way humans do."
+ *
+ * This function should only be called via naturalSortCaseSensitive and
+ * naturalSortCaseInsensitive.
+ *
+ * e.g. [3, 2, 1, 10].sort(naturalSort)
+ *
+ * @param  {Object} a
+ *         Passed in by Array.sort(a, b)
+ * @param  {Object} b
+ *         Passed in by Array.sort(a, b)
+ * @param  {Boolean} insensitive
+ *         Should the search be case insensitive?
+ */
+function naturalSort(a, b, insensitive) {
+  // convert all to strings strip whitespace
+  let i = function (s) {
+    return (insensitive && ("" + s).toLowerCase() || "" + s)
+                                   .replace(sre, "");
+  };
+  let x = i(a) || "";
+  let y = i(b) || "";
+  // chunk/tokenize
+  let xN = x.replace(re, "\0$1\0").replace(e0re, "").replace(b0re, "").split("\0");
+  let yN = y.replace(re, "\0$1\0").replace(e0re, "").replace(b0re, "").split("\0");
+  // numeric, hex or date detection
+  let xD = parseInt(x.match(hre), 16) || (xN.length !== 1 && Date.parse(x));
+  let yD = parseInt(y.match(hre), 16) || xD && y.match(dre) && Date.parse(y) || null;
+  let normChunk = function (s, l) {
+    // normalize spaces; find floats not starting with '0', string or 0 if
+    // not defined (Clint Priest)
+    return (!s.match(ore) || l == 1) &&
+           parseFloat(s) || s.replace(snre, " ").replace(sre, "") || 0;
+  };
+  let oFxNcL;
+  let oFyNcL;
+
+  // first try and sort Hex codes or Dates
+  if (yD) {
+    if (xD < yD) {
+      return -1;
+    } else if (xD > yD) {
+      return 1;
+    }
+  }
+
+  // natural sorting through split numeric strings and default strings
+  // eslint-disable-next-line
+  for (let cLoc = 0, xNl = xN.length, yNl = yN.length, numS = Math.max(xNl, yNl); cLoc < numS; cLoc++) {
+    oFxNcL = normChunk(xN[cLoc] || "", xNl);
+    oFyNcL = normChunk(yN[cLoc] || "", yNl);
+
+    // handle numeric vs string comparison - number < string - (Kyle Adams)
+    if (isNaN(oFxNcL) !== isNaN(oFyNcL)) {
+      return isNaN(oFxNcL) ? 1 : -1;
+    }
+    // if unicode use locale comparison
+    // eslint-disable-next-line
+    if (/[^\x00-\x80]/.test(oFxNcL + oFyNcL) && oFxNcL.localeCompare) {
+      let comp = oFxNcL.localeCompare(oFyNcL);
+      return comp / Math.abs(comp);
+    }
+    if (oFxNcL < oFyNcL) {
+      return -1;
+    } else if (oFxNcL > oFyNcL) {
+      return 1;
+    }
+  }
+  return null;
+}
--- a/devtools/client/shared/widgets/TableWidget.js
+++ b/devtools/client/shared/widgets/TableWidget.js
@@ -3,16 +3,18 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 "use strict";
 
 const EventEmitter = require("devtools/shared/event-emitter");
 loader.lazyRequireGetter(this, "setNamedTimeout",
   "devtools/client/shared/widgets/view-helpers", true);
 loader.lazyRequireGetter(this, "clearNamedTimeout",
   "devtools/client/shared/widgets/view-helpers", true);
+loader.lazyRequireGetter(this, "naturalSortCaseInsensitive",
+  "devtools/client/shared/natural-sort", true);
 const {KeyCodes} = require("devtools/client/shared/keycodes");
 
 const XUL_NS = "http://www.mozilla.org/keymaster/gatekeeper/there.is.only.xul";
 const HTML_NS = "http://www.w3.org/1999/xhtml";
 const AFTER_SCROLL_DELAY = 100;
 
 // Different types of events emitted by the Various components of the
 // TableWidget.
@@ -1268,21 +1270,21 @@ Column.prototype = {
    */
   push: function (item) {
     let value = item[this.id];
 
     if (this.sorted) {
       let index;
       if (this.sorted == 1) {
         index = this.cells.findIndex(element => {
-          return value < element.value;
+          return naturalSortCaseInsensitive(value, element.value) === -1;
         });
       } else {
         index = this.cells.findIndex(element => {
-          return value > element.value;
+          return naturalSortCaseInsensitive(value, element.value) === 1;
         });
       }
       index = index >= 0 ? index : this.cells.length;
       if (index < this.cells.length) {
         this._itemsDirty = true;
       }
       this.items[item[this.uniqueId]] = index;
       this.cells.splice(index, 0, new Cell(this, item, this.cells[index]));
@@ -1400,25 +1402,25 @@ Column.prototype = {
   sort: function (items) {
     // Only sort the array if we are sorting based on this column
     if (this.sorted == 1) {
       items.sort((a, b) => {
         let val1 = (a[this.id] instanceof Node) ?
             a[this.id].textContent : a[this.id];
         let val2 = (b[this.id] instanceof Node) ?
             b[this.id].textContent : b[this.id];
-        return val1 > val2;
+        return naturalSortCaseInsensitive(val1, val2);
       });
     } else if (this.sorted > 1) {
       items.sort((a, b) => {
         let val1 = (a[this.id] instanceof Node) ?
             a[this.id].textContent : a[this.id];
         let val2 = (b[this.id] instanceof Node) ?
             b[this.id].textContent : b[this.id];
-        return val2 > val1;
+        return naturalSortCaseInsensitive(val2, val1);
       });
     }
 
     if (this.selectedRow) {
       this.cells[this.items[this.selectedRow]].toggleClass("theme-selected");
     }
     this.items = {};
     // Otherwise, just use the sorted array passed to update the cells value.
--- a/devtools/client/storage/test/browser_storage_overflow.js
+++ b/devtools/client/storage/test/browser_storage_overflow.js
@@ -1,41 +1,58 @@
 // Test endless scrolling when a lot of items are present in the storage
 // inspector table.
 "use strict";
 
+const ITEMS_PER_PAGE = 50;
+
 add_task(function* () {
   yield openTabAndSetupStorage(MAIN_DOMAIN + "storage-overflow.html");
 
-  let $ = id => gPanelWindow.document.querySelector(id);
-  let $$ = sel => gPanelWindow.document.querySelectorAll(sel);
-
   gUI.tree.expandAll();
   yield selectTreeItem(["localStorage", "http://test1.example.org"]);
+  checkCellLength(ITEMS_PER_PAGE);
 
+  yield scroll();
+  checkCellLength(ITEMS_PER_PAGE * 2);
+
+  yield scroll();
+  checkCellLength(ITEMS_PER_PAGE * 3);
+
+  // Check that the columns are sorted in a human readable way (ascending).
+  checkCellValues("ASC");
+
+  // Sort descending.
+  clickColumnHeader("name");
+
+  // Check that the columns are sorted in a human readable way (descending).
+  checkCellValues("DEC");
+
+  yield finishTests();
+});
+
+function checkCellLength(len) {
+  let cells = gPanelWindow.document
+                          .querySelectorAll("#name .table-widget-cell");
+  let msg = `Table should initially display ${len} items`;
+
+  is(cells.length, len, msg);
+}
+
+function checkCellValues(order) {
+  let cells = [...gPanelWindow.document
+                              .querySelectorAll("#name .table-widget-cell")];
+  cells.forEach(function (cell, index, arr) {
+    let i = order === "ASC" ? index + 1 : arr.length - index;
+    is(cell.value, `item-${i}`, `Cell value is correct (${order}).`);
+  });
+}
+
+function* scroll() {
+  let $ = id => gPanelWindow.document.querySelector(id);
   let table = $("#storage-table .table-widget-body");
-  let cellHeight = $(".table-widget-cell").getBoundingClientRect().height;
-
-  is($$("#value .table-widget-cell").length, 50,
-     "Table should initially display 50 items");
+  let cell = $("#name .table-widget-cell");
+  let cellHeight = cell.getBoundingClientRect().height;
 
   let onStoresUpdate = gUI.once("store-objects-updated");
   table.scrollTop += cellHeight * 50;
   yield onStoresUpdate;
-
-  is($$("#value .table-widget-cell").length, 100,
-     "Table should display 100 items after scrolling");
-
-  onStoresUpdate = gUI.once("store-objects-updated");
-  table.scrollTop += cellHeight * 50;
-  yield onStoresUpdate;
-
-  is($$("#value .table-widget-cell").length, 150,
-     "Table should display 150 items after scrolling");
-
-  onStoresUpdate = gUI.once("store-objects-updated");
-  table.scrollTop += cellHeight * 50;
-  yield onStoresUpdate;
-
-  is($$("#value .table-widget-cell").length, 160,
-     "Table should display all 160 items after scrolling");
-  yield finishTests();
-});
+}
--- a/devtools/client/storage/test/head.js
+++ b/devtools/client/storage/test/head.js
@@ -752,16 +752,30 @@ function showColumn(id, state) {
   if (state) {
     column.wrapper.removeAttribute("hidden");
   } else {
     column.wrapper.setAttribute("hidden", true);
   }
 }
 
 /**
+ * Toggle sort direction on a column by clicking on the column header.
+ *
+ * @param  {String} id
+ *         The uniqueId of the given column.
+ */
+function clickColumnHeader(id) {
+  let columns = gUI.table.columns;
+  let column = columns.get(id);
+  let header = column.header;
+
+  header.click();
+}
+
+/**
  * Show or hide all columns.
  *
  * @param  {Boolean} state
  *         true = show, false = hide
  */
 function showAllColumns(state) {
   let columns = gUI.table.columns;
 
--- a/devtools/client/storage/test/storage-overflow.html
+++ b/devtools/client/storage/test/storage-overflow.html
@@ -6,14 +6,14 @@ Bug 1171903 - Storage Inspector endless 
 <head>
   <meta charset="utf-8">
   <title>Storage inspector endless scrolling test</title>
 </head>
 <body>
 <script type="text/javascript">
 "use strict";
 
-for (let i = 0; i < 160; i++) {
+for (let i = 1; i < 151; i++) {
   localStorage.setItem(`item-${i}`, `value-${i}`);
 }
 </script>
 </body>
 </html>
--- a/devtools/server/actors/storage.js
+++ b/devtools/server/actors/storage.js
@@ -10,16 +10,19 @@ const protocol = require("devtools/share
 const {LongStringActor} = require("devtools/server/actors/string");
 const {DebuggerServer} = require("devtools/server/main");
 const Services = require("Services");
 const promise = require("promise");
 const {isWindowIncluded} = require("devtools/shared/layout/utils");
 const specs = require("devtools/shared/specs/storage");
 const { Task } = require("devtools/shared/task");
 
+loader.lazyRequireGetter(this, "naturalSortCaseInsensitive",
+  "devtools/client/shared/natural-sort", true);
+
 // GUID to be used as a separator in compound keys. This must match the same
 // constant in devtools/client/storage/ui.js,
 // devtools/client/storage/test/head.js and
 // devtools/server/tests/browser/head.js
 const SEPARATOR_GUID = "{9d414cc5-8319-0a04-0586-c0a6ae01670a}";
 
 loader.lazyImporter(this, "OS", "resource://gre/modules/osfile.jsm");
 loader.lazyImporter(this, "Sqlite", "resource://gre/modules/Sqlite.jsm");
@@ -352,43 +355,51 @@ StorageActors.defaults = function (typeN
           if (result) {
             toReturn.data.push(...result.data);
           } else if (objectStores) {
             toReturn.data.push(...objectStores);
           } else {
             toReturn.data.push(...values);
           }
         }
+
         toReturn.total = this.getObjectsSize(host, names, options);
+
         if (offset > toReturn.total) {
           // In this case, toReturn.data is an empty array.
           toReturn.offset = toReturn.total;
           toReturn.data = [];
         } else {
-          toReturn.data = toReturn.data.sort((a, b) => {
-            return a[sortOn] - b[sortOn];
-          }).slice(offset, offset + size).map(a => this.toStoreObject(a));
+          // We need to use natural sort before slicing.
+          let sorted = toReturn.data.sort((a, b) => {
+            return naturalSortCaseInsensitive(a[sortOn], b[sortOn]);
+          });
+          let sliced = sorted.slice(offset, offset + size);
+          toReturn.data = sliced.map(a => this.toStoreObject(a));
         }
       } else {
         let obj = yield this.getValuesForHost(host, undefined, undefined,
                                               this.hostVsStores, principal);
         if (obj.dbs) {
           obj = obj.dbs;
         }
 
         toReturn.total = obj.length;
+
         if (offset > toReturn.total) {
           // In this case, toReturn.data is an empty array.
           toReturn.offset = offset = toReturn.total;
           toReturn.data = [];
         } else {
-          toReturn.data = obj.sort((a, b) => {
-            return a[sortOn] - b[sortOn];
-          }).slice(offset, offset + size)
-            .map(object => this.toStoreObject(object));
+          // We need to use natural sort before slicing.
+          let sorted = obj.sort((a, b) => {
+            return naturalSortCaseInsensitive(a[sortOn], b[sortOn]);
+          });
+          let sliced = sorted.slice(offset, offset + size);
+          toReturn.data = sliced.map(object => this.toStoreObject(object));
         }
       }
 
       return toReturn;
     })
   };
 };
 
--- a/toolkit/content/license.html
+++ b/toolkit/content/license.html
@@ -124,16 +124,17 @@
       <li><a href="about:license#libjingle">libjingle License</a></li>
       <li><a href="about:license#libnestegg">libnestegg License</a></li>
       <li><a href="about:license#libsoundtouch">libsoundtouch License</a></li>
       <li><a href="about:license#libyuv">libyuv License</a></li>
       <li><a href="about:license#hunspell-lt">Lithuanian Spellchecking Dictionary License</a></li>
       <li><a href="about:license#lodash">lodash License</a></li>
       <li><a href="about:license#microformatsshiv">MIT license — microformat-shiv</a></li>
       <li><a href="about:license#myspell">MySpell License</a></li>
+      <li><a href="about:license#naturalSort">naturalSort License</a></li>
       <li><a href="about:license#nicer">nICEr License</a></li>
       <li><a href="about:license#node-md5">node-md5 License</a></li>
       <li><a href="about:license#node-properties">node-properties License</a></li>
       <li><a href="about:license#nrappkit">nrappkit License</a></li>
       <li><a href="about:license#openaes">OpenAES License</a></li>
       <li><a href="about:license#openvision">OpenVision License</a></li>
 #if defined(XP_WIN) || defined(XP_MACOSX) || defined(XP_LINUX)
       <li><a href="about:license#openvr">OpenVR License</a></li>
@@ -4350,16 +4351,46 @@ BUT NOT LIMITED TO, PROCUREMENT OF SUBST
 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 SUCH DAMAGE.
 </pre>
 
 
+<hr>
+
+<h1><a id="naturalSort"></a>naturalSort License</h1>
+
+<p>This license applies to <span class="path">devtools/client/shared/natural-sort.js</span>.</p>
+
+<pre>
+The MIT License (MIT)
+
+Copyright (c) 2014 Gabriel Llamas
+
+Permission is hereby granted, free of charge, to any person obtaining a copy
+of this software and associated documentation files (the "Software"), to deal
+in the Software without restriction, including without limitation the rights
+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the Software is
+furnished to do so, subject to the following conditions:
+
+The above copyright notice and this permission notice shall be included in
+all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+THE SOFTWARE.
+</pre>
+
     <hr>
 
     <h1><a id="nicer"></a>nICEr License</h1>
 
     <p>This license applies to certain files in the directory
     <span class="path">media/mtransport/third_party/nICEr</span>.</p>
 
 <pre>