Skip to content

Commit 5d5f723

Browse files
committed
[Perf] utils: make compact O(n) via a side-channel visited-set instead of Array.indexOf
`compact` tracked visited sub-objects in a plain array and tested membership with `refs.indexOf(val)` (O(n) per lookup), so the final graph walk was O(V^2) in the number of distinct sub-objects. Replace the array with a `side-channel` (already a dependency, already used in this file for `overflowChannel`) for O(1) membership, making the walk O(V). Membership semantics are identical, so circular-reference dedup is unchanged. `side-channel` is WeakMap-backed on modern engines and degrades gracefully on old ones, so this keeps `engines.node >= 0.6` (unlike a native `Set`/`WeakMap`).
1 parent 52afe00 commit 5d5f723

2 files changed

Lines changed: 18 additions & 3 deletions

File tree

‎lib/utils.js‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -292,7 +292,7 @@ var encode = function encode(str, defaultEncoder, charset, kind, format) {
292292

293293
var compact = function compact(value) {
294294
var queue = [{ obj: { o: value }, prop: 'o' }];
295-
var refs = [];
295+
var refs = getSideChannel();
296296

297297
for (var i = 0; i < queue.length; ++i) {
298298
var item = queue[i];
@@ -302,9 +302,9 @@ var compact = function compact(value) {
302302
for (var j = 0; j < keys.length; ++j) {
303303
var key = keys[j];
304304
var val = obj[key];
305-
if (typeof val === 'object' && val !== null && refs.indexOf(val) === -1) {
305+
if (typeof val === 'object' && val !== null && !refs.has(val)) {
306306
queue[queue.length] = { obj: obj, prop: key };
307-
refs[refs.length] = val;
307+
refs.set(val, true);
308308
}
309309
}
310310
}

‎test/parse.js‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -726,6 +726,21 @@ test('parse()', function (t) {
726726
st.end();
727727
});
728728

729+
t.test('does not crash on multi-step circular references', function (st) {
730+
var a = {};
731+
a.b = { c: { d: a } };
732+
733+
var parsed;
734+
735+
st.doesNotThrow(function () {
736+
parsed = qs.parse({ foo: a });
737+
});
738+
739+
st.equal('foo' in parsed, true, 'parsed has "foo" property');
740+
st.equal(parsed.foo.b.c.d, parsed.foo, 'the multi-step cycle is preserved');
741+
st.end();
742+
});
743+
729744
t.test('does not crash when parsing deep objects', function (st) {
730745
var parsed;
731746
var str = 'foo';

0 commit comments

Comments
 (0)