Skip to content

Commit 02d1e32

Browse files
TimothyGuTimothyGu
committed
url: add urlSearchParams.sort()
PR-URL: #11098 Fixes: #10760 Ref: whatwg/url#26 Ref: whatwg/url#199 Ref: web-platform-tests/wpt#4531 Reviewed-By: James M Snell <[email protected]> Reviewed-By: Joyee Cheung <[email protected]>
1 parent a2fac32 commit 02d1e32

File tree

3 files changed

+174
-0
lines changed

3 files changed

+174
-0
lines changed

‎doc/api/url.md‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -777,6 +777,21 @@ Returns an ES6 Iterator over the names of each name-value pair.
777777
Remove any existing name-value pairs whose name is `name` and append a new
778778
name-value pair.
779779

780+
#### urlSearchParams.sort()
781+
782+
Sort all existing name-value pairs in-place by their names. Sorting is done
783+
with a [stable sorting algorithm][], so relative order between name-value pairs
784+
with the same name is preserved.
785+
786+
This method can be used, in particular, to increase cache hits.
787+
788+
```js
789+
const params = new URLSearchParams('query[]=abc&type=search&query[]=123');
790+
params.sort();
791+
console.log(params.toString());
792+
// Prints query%5B%5D=abc&query%5B%5D=123&type=search
793+
```
794+
780795
#### urlSearchParams.toString()
781796

782797
* Returns: {String}
@@ -872,3 +887,4 @@ console.log(myURL.origin);
872887
[`Map`]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map
873888
[`array.toString()`]: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/toString
874889
[WHATWG URL]: #url_the_whatwg_url_api
890+
[stable sorting algorithm]: https://en.wikipedia.org/wiki/Sorting_algorithm#Stability

‎lib/internal/url.js‎

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -766,6 +766,35 @@ class URLSearchParams {
766766
}
767767
}
768768

769+
// for merge sort
770+
function merge(out, start, mid, end, lBuffer, rBuffer) {
771+
const sizeLeft = mid - start;
772+
const sizeRight = end - mid;
773+
var l, r, o;
774+
775+
for (l = 0; l < sizeLeft; l++)
776+
lBuffer[l] = out[start + l];
777+
for (r = 0; r < sizeRight; r++)
778+
rBuffer[r] = out[mid + r];
779+
780+
l = 0;
781+
r = 0;
782+
o = start;
783+
while (l < sizeLeft && r < sizeRight) {
784+
if (lBuffer[l] <= rBuffer[r]) {
785+
out[o++] = lBuffer[l++];
786+
out[o++] = lBuffer[l++];
787+
} else {
788+
out[o++] = rBuffer[r++];
789+
out[o++] = rBuffer[r++];
790+
}
791+
}
792+
while (l < sizeLeft)
793+
out[o++] = lBuffer[l++];
794+
while (r < sizeRight)
795+
out[o++] = rBuffer[r++];
796+
}
797+
769798
defineIDLClass(URLSearchParams.prototype, 'URLSearchParams', {
770799
append(name, value) {
771800
if (!this || !(this instanceof URLSearchParams)) {
@@ -897,6 +926,51 @@ defineIDLClass(URLSearchParams.prototype, 'URLSearchParams', {
897926
update(this[context], this);
898927
},
899928

929+
sort() {
930+
const a = this[searchParams];
931+
const len = a.length;
932+
if (len <= 2) {
933+
return;
934+
}
935+
936+
// arbitrary number found through testing
937+
if (len < 100) {
938+
// Simple stable in-place insertion sort
939+
// Derived from v8/src/js/array.js
940+
for (var i = 2; i < len; i += 2) {
941+
var curKey = a[i];
942+
var curVal = a[i + 1];
943+
var j;
944+
for (j = i - 2; j >= 0; j -= 2) {
945+
if (a[j] > curKey) {
946+
a[j + 2] = a[j];
947+
a[j + 3] = a[j + 1];
948+
} else {
949+
break;
950+
}
951+
}
952+
a[j + 2] = curKey;
953+
a[j + 3] = curVal;
954+
}
955+
} else {
956+
// Bottom-up iterative stable merge sort
957+
const lBuffer = new Array(len);
958+
const rBuffer = new Array(len);
959+
for (var step = 2; step < len; step *= 2) {
960+
for (var start = 0; start < len - 2; start += 2 * step) {
961+
var mid = start + step;
962+
var end = mid + step;
963+
end = end < len ? end : len;
964+
if (mid > end)
965+
continue;
966+
merge(a, start, mid, end, lBuffer, rBuffer);
967+
}
968+
}
969+
}
970+
971+
update(this[context], this);
972+
},
973+
900974
// https://heycam.github.io/webidl/#es-iterators
901975
// Define entries here rather than [Symbol.iterator] as the function name
902976
// must be set to `entries`.

‎test/parallel/test-whatwg-url-searchparams-sort.js‎

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
'use strict';
2+
3+
const common = require('../common');
4+
const { URL, URLSearchParams } = require('url');
5+
const { test, assert_array_equals } = common.WPT;
6+
7+
/* eslint-disable */
8+
/* WPT Refs:
9+
https://github.com/w3c/web-platform-tests/blob/5903e00e77e85f8bcb21c73d1d7819fcd04763bd/url/urlsearchparams-sort.html
10+
License: http://www.w3.org/Consortium/Legal/2008/04-testsuite-copyright.html
11+
*/
12+
[
13+
{
14+
"input": "z=b&a=b&z=a&a=a",
15+
"output": [["a", "b"], ["a", "a"], ["z", "b"], ["z", "a"]]
16+
},
17+
{
18+
"input": "\uFFFD=x&\uFFFC&\uFFFD=a",
19+
"output": [["\uFFFC", ""], ["\uFFFD", "x"], ["\uFFFD", "a"]]
20+
},
21+
{
22+
"input": "ffi&🌈", // 🌈 > code point, but < code unit because two code units
23+
"output": [["🌈", ""], ["ffi", ""]]
24+
},
25+
{
26+
"input": "é&e\uFFFD&e\u0301",
27+
"output": [["e\u0301", ""], ["e\uFFFD", ""], ["é", ""]]
28+
},
29+
{
30+
"input": "z=z&a=a&z=y&a=b&z=x&a=c&z=w&a=d&z=v&a=e&z=u&a=f&z=t&a=g",
31+
"output": [["a", "a"], ["a", "b"], ["a", "c"], ["a", "d"], ["a", "e"], ["a", "f"], ["a", "g"], ["z", "z"], ["z", "y"], ["z", "x"], ["z", "w"], ["z", "v"], ["z", "u"], ["z", "t"]]
32+
}
33+
].forEach((val) => {
34+
test(() => {
35+
let params = new URLSearchParams(val.input),
36+
i = 0
37+
params.sort()
38+
for(let param of params) {
39+
assert_array_equals(param, val.output[i])
40+
i++
41+
}
42+
}, "Parse and sort: " + val.input)
43+
44+
test(() => {
45+
let url = new URL("?" + val.input, "https://example/")
46+
url.searchParams.sort()
47+
let params = new URLSearchParams(url.search),
48+
i = 0
49+
for(let param of params) {
50+
assert_array_equals(param, val.output[i])
51+
i++
52+
}
53+
}, "URL parse and sort: " + val.input)
54+
})
55+
/* eslint-enable */
56+
57+
// Tests below are not from WPT.
58+
;[
59+
{
60+
'input': 'z=a&=b&c=d',
61+
'output': [['', 'b'], ['c', 'd'], ['z', 'a']]
62+
}
63+
].forEach((val) => {
64+
test(() => {
65+
const params = new URLSearchParams(val.input);
66+
let i = 0;
67+
params.sort();
68+
for (const param of params) {
69+
assert_array_equals(param, val.output[i]);
70+
i++;
71+
}
72+
}, 'Parse and sort: ' + val.input);
73+
74+
test(() => {
75+
const url = new URL(`?${val.input}`, 'https://example/');
76+
url.searchParams.sort();
77+
const params = new URLSearchParams(url.search);
78+
let i = 0;
79+
for (const param of params) {
80+
assert_array_equals(param, val.output[i]);
81+
i++;
82+
}
83+
}, 'URL parse and sort: ' + val.input);
84+
});

0 commit comments

Comments
 (0)