url: improving URLSearchParams

- add some benchmarks for URLSearchParams
- change URLSearchParams backing store to an array
- add custom inspection for URLSearchParams and its iterators

PR-URL: https://github.com/nodejs/node/pull/10399
Reviewed-By: James M Snell <jasnell@gmail.com>

6 files changed, 369 insertions, 43 deletions

diff --git a/benchmark/url/url-searchparams-iteration.js b/benchmark/url/url-searchparams-iteration.js
new file mode 100644
index 00000000000..caa4e45c412
--- /dev/null
+++ b/benchmark/url/url-searchparams-iteration.js
@@ -0,0 +1,60 @@
+'use strict';
+const common = require('../common.js');
+const assert = require('assert');
+const URLSearchParams = new (require('url').URL)('a:').searchParams.constructor;
+
+const bench = common.createBenchmark(main, {
+  method: ['forEach', 'iterator'],
+  n: [1e6]
+});
+
+const str = 'one=single&two=first&three=first&two=2nd&three=2nd&three=3rd';
+
+function forEach(n) {
+  const params = new URLSearchParams(str);
+  const noDead = [];
+  const cb = (val, key) => {
+    noDead[0] = key;
+    noDead[1] = val;
+  };
+
+  bench.start();
+  for (var i = 0; i < n; i += 1)
+    params.forEach(cb);
+  bench.end(n);
+
+  assert.strictEqual(noDead[0], 'three');
+  assert.strictEqual(noDead[1], '3rd');
+}
+
+function iterator(n) {
+  const params = new URLSearchParams(str);
+  const noDead = [];
+
+  bench.start();
+  for (var i = 0; i < n; i += 1)
+    for (var pair of params) {
+      noDead[0] = pair[0];
+      noDead[1] = pair[1];
+    }
+  bench.end(n);
+
+  assert.strictEqual(noDead[0], 'three');
+  assert.strictEqual(noDead[1], '3rd');
+}
+
+function main(conf) {
+  const method = conf.method;
+  const n = conf.n | 0;
+
+  switch (method) {
+    case 'forEach':
+      forEach(n);
+      break;
+    case 'iterator':
+      iterator(n);
+      break;
+    default:
+      throw new Error('Unknown method');
+  }
+}
diff --git a/benchmark/url/url-searchparams-parse.js b/benchmark/url/url-searchparams-parse.js
new file mode 100644
index 00000000000..61796a7d327
--- /dev/null
+++ b/benchmark/url/url-searchparams-parse.js
@@ -0,0 +1,31 @@
+'use strict';
+const common = require('../common.js');
+const URLSearchParams = new (require('url').URL)('a:').searchParams.constructor;
+
+const inputs = {
+  noencode: 'foo=bar&baz=quux&xyzzy=thud',
+  // multicharsep: 'foo=bar&&&&&&&&&&baz=quux&&&&&&&&&&xyzzy=thud',
+  multicharsep: '&&&&&&&&&&&&&&&&&&&&&&&&&&&&',
+  encodemany: '%66%6F%6F=bar&%62%61%7A=quux&xyzzy=%74h%75d',
+  encodelast: 'foo=bar&baz=quux&xyzzy=thu%64',
+  multivalue: 'foo=bar&foo=baz&foo=quux&quuy=quuz',
+  multivaluemany: 'foo=bar&foo=baz&foo=quux&quuy=quuz&foo=abc&foo=def&' +
+                  'foo=ghi&foo=jkl&foo=mno&foo=pqr&foo=stu&foo=vwxyz',
+  manypairs: 'a&b&c&d&e&f&g&h&i&j&k&l&m&n&o&p&q&r&s&t&u&v&w&x&y&z'
+};
+
+const bench = common.createBenchmark(main, {
+  type: Object.keys(inputs),
+  n: [1e5]
+});
+
+function main(conf) {
+  const input = inputs[conf.type];
+  const n = conf.n | 0;
+
+  var i;
+  bench.start();
+  for (i = 0; i < n; i++)
+    new URLSearchParams(input);
+  bench.end(n);
+}
diff --git a/benchmark/url/url-searchparams-read.js b/benchmark/url/url-searchparams-read.js
new file mode 100644
index 00000000000..4cee49c74d2
--- /dev/null
+++ b/benchmark/url/url-searchparams-read.js
@@ -0,0 +1,58 @@
+'use strict';
+const common = require('../common.js');
+const URLSearchParams = new (require('url').URL)('a:').searchParams.constructor;
+
+const bench = common.createBenchmark(main, {
+  method: ['get', 'getAll', 'has'],
+  param: ['one', 'two', 'three', 'nonexistent'],
+  n: [1e6]
+});
+
+const str = 'one=single&two=first&three=first&two=2nd&three=2nd&three=3rd';
+
+function get(n, param) {
+  const params = new URLSearchParams(str);
+
+  bench.start();
+  for (var i = 0; i < n; i += 1)
+    params.get(param);
+  bench.end(n);
+}
+
+function getAll(n, param) {
+  const params = new URLSearchParams(str);
+
+  bench.start();
+  for (var i = 0; i < n; i += 1)
+    params.getAll(param);
+  bench.end(n);
+}
+
+function has(n, param) {
+  const params = new URLSearchParams(str);
+
+  bench.start();
+  for (var i = 0; i < n; i += 1)
+    params.has(param);
+  bench.end(n);
+}
+
+function main(conf) {
+  const method = conf.method;
+  const param = conf.param;
+  const n = conf.n | 0;
+
+  switch (method) {
+    case 'get':
+      get(n, param);
+      break;
+    case 'getAll':
+      getAll(n, param);
+      break;
+    case 'has':
+      has(n, param);
+      break;
+    default:
+      throw new Error('Unknown method');
+  }
+}
diff --git a/benchmark/url/url-searchparams-stringifier.js b/benchmark/url/url-searchparams-stringifier.js
new file mode 100644
index 00000000000..2979064b322
--- /dev/null
+++ b/benchmark/url/url-searchparams-stringifier.js
@@ -0,0 +1,35 @@
+'use strict';
+const common = require('../common.js');
+const Buffer = require('buffer').Buffer;
+const URLSearchParams = new (require('url').URL)('a:').searchParams.constructor;
+
+const inputs = {
+  noencode: 'foo=bar&baz=quux&xyzzy=thud',
+  // multicharsep: 'foo=bar&&&&&&&&&&baz=quux&&&&&&&&&&xyzzy=thud',
+  multicharsep: '&&&&&&&&&&&&&&&&&&&&&&&&&&&&',
+  encodemany: '%66%6F%6F=bar&%62%61%7A=quux&xyzzy=%74h%75d',
+  encodelast: 'foo=bar&baz=quux&xyzzy=thu%64',
+  multivalue: 'foo=bar&foo=baz&foo=quux&quuy=quuz',
+  multivaluemany: 'foo=bar&foo=baz&foo=quux&quuy=quuz&foo=abc&foo=def&' +
+                  'foo=ghi&foo=jkl&foo=mno&foo=pqr&foo=stu&foo=vwxyz',
+  manypairs: 'a&b&c&d&e&f&g&h&i&j&k&l&m&n&o&p&q&r&s&t&u&v&w&x&y&z'
+};
+
+const bench = common.createBenchmark(main, {
+  type: Object.keys(inputs),
+  n: [1e5]
+});
+
+function main(conf) {
+  const input = inputs[conf.type];
+  const n = conf.n | 0;
+
+  const params = new URLSearchParams(input);
+
+  bench.start();
+  // Using Buffer.from to prevent JS version from cheating with ropes instead
+  // of strings
+  for (var i = 0; i < n; i += 1)
+    Buffer.from(params.toString());
+  bench.end(n);
+}
diff --git a/lib/internal/url.js b/lib/internal/url.js
index 9815d035a15..302e54a378f 100644
--- a/lib/internal/url.js
+++ b/lib/internal/url.js
@@ -8,6 +8,7 @@ function getPunycode() {
   }
 }
 const punycode = getPunycode();
+const util = require('util');
 const binding = process.binding('url');
 const context = Symbol('context');
 const cannotBeBase = Symbol('cannot-be-base');
@@ -493,7 +494,7 @@ Object.defineProperties(URL.prototype, {
       ctx.query = '';
       binding.parse(search, binding.kQuery, null, ctx,
                     onParseSearchComplete.bind(this));
-      this[searchParams][searchParams] = querystring.parse(search);
+      initSearchParams(this[searchParams], search);
     }
   },
   searchParams: {  // readonly
@@ -610,8 +611,13 @@ function update(url, params) {
   }
 }
 
-function getSearchParamPairs(target) {
-  const obj = target[searchParams];
+// Reused by the URL parse function invoked by
+// the href setter, and the URLSearchParams constructor
+function initSearchParams(url, init) {
+  url[searchParams] = getParamsFromObject(querystring.parse(init));
+}
+
+function getParamsFromObject(obj) {
   const keys = Object.keys(obj);
   const values = [];
   for (var i = 0; i < keys.length; i++) {
@@ -619,25 +625,33 @@ function getSearchParamPairs(target) {
     const value = obj[name];
     if (Array.isArray(value)) {
       for (const item of value)
-        values.push([name, item]);
+        values.push(name, item);
     } else {
-      values.push([name, value]);
+      values.push(name, value);
     }
   }
   return values;
 }
 
-// Reused by the URL parse function invoked by
-// the href setter, and the URLSearchParams constructor
-function initSearchParams(url, init) {
-  url[searchParams] = querystring.parse(init);
+function getObjectFromParams(array) {
+  const obj = new StorageObject();
+  for (var i = 0; i < array.length; i += 2) {
+    const name = array[i];
+    const value = array[i + 1];
+    if (obj[name]) {
+      obj[name].push(value);
+    } else {
+      obj[name] = [value];
+    }
+  }
+  return obj;
 }
 
 class URLSearchParams {
   constructor(init = '') {
     if (init instanceof URLSearchParams) {
       const childParams = init[searchParams];
-      this[searchParams] = Object.assign(Object.create(null), childParams);
+      this[searchParams] = childParams.slice();
     } else {
       init = String(init);
       if (init[0] === '?') init = init.slice(1);
@@ -662,17 +676,9 @@ class URLSearchParams {
         'Both `name` and `value` arguments need to be specified');
     }
 
-    const obj = this[searchParams];
     name = String(name);
     value = String(value);
-    var existing = obj[name];
-    if (existing === undefined) {
-      obj[name] = value;
-    } else if (Array.isArray(existing)) {
-      existing.push(value);
-    } else {
-      obj[name] = [existing, value];
-    }
+    this[searchParams].push(name, value);
     update(this[context], this);
   }
 
@@ -684,9 +690,16 @@ class URLSearchParams {
       throw new TypeError('The `name` argument needs to be specified');
     }
 
-    const obj = this[searchParams];
+    const list = this[searchParams];
     name = String(name);
-    delete obj[name];
+    for (var i = 0; i < list.length;) {
+      const cur = list[i];
+      if (cur === name) {
+        list.splice(i, 2);
+      } else {
+        i += 2;
+      }
+    }
     update(this[context], this);
   }
 
@@ -699,10 +712,35 @@ class URLSearchParams {
         'Both `name` and `value` arguments need to be specified');
     }
 
-    const obj = this[searchParams];
+    const list = this[searchParams];
     name = String(name);
     value = String(value);
-    obj[name] = value;
+
+    // If there are any name-value pairs whose name is `name`, in `list`, set
+    // the value of the first such name-value pair to `value` and remove the
+    // others.
+    var found = false;
+    for (var i = 0; i < list.length;) {
+      const cur = list[i];
+      if (cur === name) {
+        if (!found) {
+          list[i + 1] = value;
+          found = true;
+          i += 2;
+        } else {
+          list.splice(i, 2);
+        }
+      } else {
+        i += 2;
+      }
+    }
+
+    // Otherwise, append a new name-value pair whose name is `name` and value
+    // is `value`, to `list`.
+    if (!found) {
+      list.push(name, value);
+    }
+
     update(this[context], this);
   }
 
@@ -714,10 +752,14 @@ class URLSearchParams {
       throw new TypeError('The `name` argument needs to be specified');
     }
 
-    const obj = this[searchParams];
+    const list = this[searchParams];
     name = String(name);
-    var value = obj[name];
-    return value === undefined ? null : Array.isArray(value) ? value[0] : value;
+    for (var i = 0; i < list.length; i += 2) {
+      if (list[i] === name) {
+        return list[i + 1];
+      }
+    }
+    return null;
   }
 
   getAll(name) {
@@ -728,10 +770,15 @@ class URLSearchParams {
       throw new TypeError('The `name` argument needs to be specified');
     }
 
-    const obj = this[searchParams];
+    const list = this[searchParams];
+    const values = [];
     name = String(name);
-    var value = obj[name];
-    return value === undefined ? [] : Array.isArray(value) ? value : [value];
+    for (var i = 0; i < list.length; i += 2) {
+      if (list[i] === name) {
+        values.push(list[i + 1]);
+      }
+    }
+    return values;
   }
 
   has(name) {
@@ -742,9 +789,14 @@ class URLSearchParams {
       throw new TypeError('The `name` argument needs to be specified');
     }
 
-    const obj = this[searchParams];
+    const list = this[searchParams];
     name = String(name);
-    return name in obj;
+    for (var i = 0; i < list.length; i += 2) {
+      if (list[i] === name) {
+        return true;
+      }
+    }
+    return false;
   }
 
   // https://heycam.github.io/webidl/#es-iterators
@@ -766,14 +818,16 @@ class URLSearchParams {
       throw new TypeError('The `callback` argument needs to be specified');
     }
 
-    let pairs = getSearchParamPairs(this);
+    let list = this[searchParams];
 
     var i = 0;
-    while (i < pairs.length) {
-      const [key, value] = pairs[i];
+    while (i < list.length) {
+      const key = list[i];
+      const value = list[i + 1];
       callback.call(thisArg, value, key, this);
-      pairs = getSearchParamPairs(this);
-      i++;
+      // in case the URL object's `search` is updated
+      list = this[searchParams];
+      i += 2;
     }
   }
 
@@ -800,12 +854,38 @@ class URLSearchParams {
       throw new TypeError('Value of `this` is not a URLSearchParams');
     }
 
-    return querystring.stringify(this[searchParams]);
+    return querystring.stringify(getObjectFromParams(this[searchParams]));
   }
 }
 // https://heycam.github.io/webidl/#es-iterable-entries
 URLSearchParams.prototype[Symbol.iterator] = URLSearchParams.prototype.entries;
 
+URLSearchParams.prototype[util.inspect.custom] =
+  function inspect(recurseTimes, ctx) {
+    const innerOpts = Object.assign({}, ctx);
+    if (recurseTimes !== null) {
+      innerOpts.depth = recurseTimes - 1;
+    }
+    const innerInspect = (v) => util.inspect(v, innerOpts);
+
+    const list = this[searchParams];
+    const output = [];
+    for (var i = 0; i < list.length; i += 2)
+      output.push(`${innerInspect(list[i])} => ${innerInspect(list[i + 1])}`);
+
+    const colorRe = /\u001b\[\d\d?m/g;
+    const length = output.reduce((prev, cur) => {
+      return prev + cur.replace(colorRe, '').length + ', '.length;
+    }, -', '.length);
+    if (length > ctx.breakLength) {
+      return `${this.constructor.name} {\n  ${output.join(',\n  ')} }`;
+    } else if (output.length) {
+      return `${this.constructor.name} { ${output.join(', ')} }`;
+    } else {
+      return `${this.constructor.name} {}`;
+    }
+  };
+
 // https://heycam.github.io/webidl/#dfn-default-iterator-object
 function createSearchParamsIterator(target, kind) {
   const iterator = Object.create(URLSearchParamsIteratorPrototype);
@@ -830,7 +910,7 @@ const URLSearchParamsIteratorPrototype = Object.setPrototypeOf({
       kind,
       index
     } = this[context];
-    const values = getSearchParamPairs(target);
+    const values = target[searchParams];
     const len = values.length;
     if (index >= len) {
       return {
@@ -839,22 +919,54 @@ const URLSearchParamsIteratorPrototype = Object.setPrototypeOf({
       };
     }
 
-    const pair = values[index];
-    this[context].index = index + 1;
+    const name = values[index];
+    const value = values[index + 1];
+    this[context].index = index + 2;
 
     let result;
     if (kind === 'key') {
-      result = pair[0];
+      result = name;
     } else if (kind === 'value') {
-      result = pair[1];
+      result = value;
     } else {
-      result = pair;
+      result = [name, value];
     }
 
     return {
       value: result,
       done: false
     };
+  },
+  [util.inspect.custom]: function inspect(recurseTimes, ctx) {
+    const innerOpts = Object.assign({}, ctx);
+    if (recurseTimes !== null) {
+      innerOpts.depth = recurseTimes - 1;
+    }
+    const {
+      target,
+      kind,
+      index
+    } = this[context];
+    const output = target[searchParams].slice(index).reduce((prev, cur, i) => {
+      const key = i % 2 === 0;
+      if (kind === 'key' && key) {
+        prev.push(cur);
+      } else if (kind === 'value' && !key) {
+        prev.push(cur);
+      } else if (kind === 'key+value' && !key) {
+        prev.push([target[searchParams][index + i - 1], cur]);
+      }
+      return prev;
+    }, []);
+    const breakLn = util.inspect(output, innerOpts).includes('\n');
+    const outputStrs = output.map((p) => util.inspect(p, innerOpts));
+    let outputStr;
+    if (breakLn) {
+      outputStr = `\n  ${outputStrs.join(',\n  ')}`;
+    } else {
+      outputStr = ` ${outputStrs.join(', ')}`;
+    }
+    return `${this[Symbol.toStringTag]} {${outputStr} }`;
   }
 }, IteratorPrototype);
 
diff --git a/test/parallel/test-whatwg-url-searchparams-inspect.js b/test/parallel/test-whatwg-url-searchparams-inspect.js
new file mode 100644
index 00000000000..12472e1df06
--- /dev/null
+++ b/test/parallel/test-whatwg-url-searchparams-inspect.js
@@ -0,0 +1,30 @@
+'use strict';
+
+require('../common');
+const assert = require('assert');
+const util = require('util');
+const URL = require('url').URL;
+
+// Until we export URLSearchParams
+const m = new URL('http://example.org');
+const URLSearchParams = m.searchParams.constructor;
+
+const sp = new URLSearchParams('?a=a&b=b&b=c');
+assert.strictEqual(util.inspect(sp),
+                   "URLSearchParams { 'a' => 'a', 'b' => 'b', 'b' => 'c' }");
+assert.strictEqual(util.inspect(sp.keys()),
+                   "URLSearchParamsIterator { 'a', 'b', 'b' }");
+assert.strictEqual(util.inspect(sp.values()),
+                   "URLSearchParamsIterator { 'a', 'b', 'c' }");
+
+const iterator = sp.entries();
+assert.strictEqual(util.inspect(iterator),
+                   "URLSearchParamsIterator { [ 'a', 'a' ], [ 'b', 'b' ], " +
+                                             "[ 'b', 'c' ] }");
+iterator.next();
+assert.strictEqual(util.inspect(iterator),
+                   "URLSearchParamsIterator { [ 'b', 'b' ], [ 'b', 'c' ] }");
+iterator.next();
+iterator.next();
+assert.strictEqual(util.inspect(iterator),
+                   'URLSearchParamsIterator {  }');