summaryrefslogtreecommitdiffstats
path: root/devtools/shared/natural-sort.js
blob: 0b6a30db5f1cb3cbf09cab80955c06c2a52acf3c (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/*
 * Based on the Natural Sort algorithm for Javascript - Version 0.8.1 - adapted
 * for Firefox DevTools and released under the MIT license.
 *
 * Author: Jim Palmer (based on chunking idea from Dave Koelle)
 *
 * Repository:
 *   https://github.com/overset/javascript-natural-sort/
 */

"use strict";

const tokenizeNumbersRx =
  /(^([+\-]?\d+(?:\.\d*)?(?:[eE][+\-]?\d+)?(?=\D|\s|$))|^0x[\da-fA-F]+$|\d+)/g;
const hexRx = /^0x[0-9a-f]+$/i;
const startsWithNullRx = /^\0/;
const endsWithNullRx = /\0$/;
const whitespaceRx = /\s+/g;
const startsWithZeroRx = /^0/;
const versionRx = /^([\w-]+-)?\d+\.\d+\.\d+$/;
const numericDateRx = /^\d+[- /]\d+[- /]\d+$/;

// If a string contains any of these, we'll try to parse it as a Date
const dateKeywords = [
  "mon",
  "tues",
  "wed",
  "thur",
  "fri",
  "sat",
  "sun",

  "jan",
  "feb",
  "mar",
  "apr",
  "may",
  "jun",
  "jul",
  "aug",
  "sep",
  "oct",
  "nov",
  "dec",
];

/**
 * Figures whether a given string should be considered by naturalSort to be a
 * Date, and returns the Date's timestamp if so. Some Date formats, like
 * single numbers and MM.DD.YYYY, are not supported due to conflicts with things
 * like version numbers.
 */
function tryParseDate(str) {
  const lowerCaseStr = str.toLowerCase();
  return (
    !versionRx.test(str) &&
    (numericDateRx.test(str) ||
      dateKeywords.some(s => lowerCaseStr.includes(s))) &&
    Date.parse(str)
  );
}

/**
 * Sort numbers, strings, IP Addresses, Dates, Filenames, version numbers etc.
 * "the way humans do."
 *
 * @param  {Object} a
 *         Passed in by Array.sort(a, b)
 * @param  {Object} b
 *         Passed in by Array.sort(a, b)
 * @param  {String} sessionString
 *         Client-side value of storage-expires-session l10n string.
 *         Since this function can be called from both the client and the server,
 *         and given that client and server might have different locale, we can't compute
 *         the localized string directly from here.
 * @param  {Boolean} insensitive
 *         Should the search be case insensitive?
 */
// eslint-disable-next-line complexity
function naturalSort(a = "", b = "", sessionString, insensitive = false) {
  // Ensure we are working with trimmed strings
  a = (a + "").trim();
  b = (b + "").trim();

  if (insensitive) {
    a = a.toLowerCase();
    b = b.toLowerCase();
    sessionString = sessionString.toLowerCase();
  }

  // Chunk/tokenize - Here we split the strings into arrays or strings and
  // numbers.
  const aChunks = a
    .replace(tokenizeNumbersRx, "\0$1\0")
    .replace(startsWithNullRx, "")
    .replace(endsWithNullRx, "")
    .split("\0");
  const bChunks = b
    .replace(tokenizeNumbersRx, "\0$1\0")
    .replace(startsWithNullRx, "")
    .replace(endsWithNullRx, "")
    .split("\0");

  // Hex or date detection.
  const aHexOrDate = parseInt(a.match(hexRx), 16) || tryParseDate(a);
  const bHexOrDate = parseInt(b.match(hexRx), 16) || tryParseDate(b);

  if (
    (aHexOrDate || bHexOrDate) &&
    (a === sessionString || b === sessionString)
  ) {
    // We have a date and a session string. Move "Session" above the date
    // (for session cookies)
    if (a === sessionString) {
      return -1;
    } else if (b === sessionString) {
      return 1;
    }
  }

  // Try and sort Hex codes or Dates.
  if (aHexOrDate && bHexOrDate) {
    if (aHexOrDate < bHexOrDate) {
      return -1;
    } else if (aHexOrDate > bHexOrDate) {
      return 1;
    }
    return 0;
  }

  // Natural sorting through split numeric strings and default strings
  const aChunksLength = aChunks.length;
  const bChunksLength = bChunks.length;
  const maxLen = Math.max(aChunksLength, bChunksLength);

  for (let i = 0; i < maxLen; i++) {
    const aChunk = normalizeChunk(aChunks[i] || "", aChunksLength);
    const bChunk = normalizeChunk(bChunks[i] || "", bChunksLength);

    // Handle numeric vs string comparison - number < string
    if (isNaN(aChunk) !== isNaN(bChunk)) {
      return isNaN(aChunk) ? 1 : -1;
    }

    // If unicode use locale comparison
    // eslint-disable-next-line no-control-regex
    if (/[^\x00-\x80]/.test(aChunk + bChunk) && aChunk.localeCompare) {
      const comp = aChunk.localeCompare(bChunk);
      return comp / Math.abs(comp);
    }
    if (aChunk < bChunk) {
      return -1;
    } else if (aChunk > bChunk) {
      return 1;
    }
  }
  return null;
}

// Normalize spaces; find floats not starting with '0', string or 0 if not
// defined
const normalizeChunk = function (str, length) {
  return (
    ((!str.match(startsWithZeroRx) || length == 1) && parseFloat(str)) ||
    str.replace(whitespaceRx, " ").trim() ||
    0
  );
};

exports.naturalSortCaseSensitive = function naturalSortCaseSensitive(
  a,
  b,
  sessionString
) {
  return naturalSort(a, b, sessionString, false);
};

exports.naturalSortCaseInsensitive = function naturalSortCaseInsensitive(
  a,
  b,
  sessionString
) {
  return naturalSort(a, b, sessionString, true);
};