Visitar URL original
Merge commit from fork · immutable-js/immutable-js@a1a1ee4 · GitHub
Skip to content

Commit a1a1ee4

Browse files
authored
Merge commit from fork
fix(List): guard oversized bounds in setListBounds
2 parents c221031 + f4c94e2 commit a1a1ee4

2 files changed

Lines changed: 97 additions & 2 deletions

File tree

‎__tests__/List.ts‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -956,6 +956,55 @@ describe('List', () => {
956956
});
957957
});
958958

959+
// A List addresses its values through a 32-wide trie using signed 32-bit
960+
// bitwise math. Sizes/indices at or beyond 2 ** 30 used to overflow that math:
961+
// the level-raising loop spun forever, hanging an empty List and OOM-crashing
962+
// (SIGABRT) a populated one, while `setSize` silently wrapped large values.
963+
// All of these must now throw a clear, catchable RangeError.
964+
describe('rejects out-of-range sizes instead of hanging / crashing', () => {
965+
const tooBig = 2 ** 30;
966+
967+
it('throws (does not hang) when setting a too-large index on an empty List', () => {
968+
expect(() => List().set(tooBig, 'x')).toThrow(RangeError);
969+
});
970+
971+
it('throws (does not OOM-crash) when setting a too-large index on a populated List', () => {
972+
const list = List(arrayOfSize(64));
973+
expect(() => list.set(tooBig, 'x')).toThrow(RangeError);
974+
});
975+
976+
it('throws for a numeric-string index coming through a setIn key path', () => {
977+
const state = fromJS({ items: arrayOfSize(64) });
978+
expect(() => state.setIn(['items', '1073741824'], 'x')).toThrow(
979+
RangeError
980+
);
981+
});
982+
983+
it('throws on setSize beyond the max rather than silently truncating', () => {
984+
// Previously returned size 0 and size 5 respectively.
985+
expect(() => List([1, 2, 3]).setSize(2 ** 31)).toThrow(RangeError);
986+
expect(() => List([1, 2, 3]).setSize(2 ** 32 + 5)).toThrow(RangeError);
987+
});
988+
989+
it('still allows operations within the addressable range', () => {
990+
expect(List([1, 2, 3]).setSize(1500).size).toBe(1500);
991+
expect(List([1, 2, 3]).set(5, 'x').size).toBe(6);
992+
// Largest in-range size is accepted by the bounds math (sparse, no alloc).
993+
expect(List([1, 2, 3]).setSize(tooBig).size).toBe(tooBig);
994+
});
995+
996+
it('handles a large in-range negative index without hanging', () => {
997+
// Exercises the deep-tree origin-normalization path (the `2 ** exp`
998+
// fallback). Must terminate rather than spin forever; the existing values
999+
// are shifted to the end of the grown List.
1000+
const result = List([1, 2, 3]).set(-(2 ** 29), 'x');
1001+
expect(result.size).toBe(2 ** 29);
1002+
expect(result.get(result.size - 3)).toBe(1);
1003+
expect(result.get(result.size - 2)).toBe(2);
1004+
expect(result.get(result.size - 1)).toBe(3);
1005+
});
1006+
});
1007+
9591008
it('Does not infinite loop when sliced with NaN #459', () => {
9601009
const list = List([1, 2, 3, 4, 5]);
9611010
const newList = list.slice(0, NaN);

‎src/List.js‎

Lines changed: 48 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -549,7 +549,39 @@ function listNodeFor(list, rawIndex) {
549549
}
550550
}
551551

552+
/**
553+
* Validates requested bounds before int32 coercion in setListBounds().
554+
* Throws when origin/capacity would exceed the trie's safe range.
555+
*/
556+
function validateListBoundsRequest(list, begin, end) {
557+
const requestedOrigin = list._origin + (begin === undefined ? 0 : begin);
558+
const requestedCapacity =
559+
end === undefined
560+
? list._capacity
561+
: end < 0
562+
? list._capacity + end
563+
: list._origin + end;
564+
565+
// Keep origin/capacity within the trie's safe signed 32-bit range.
566+
if (
567+
(Number.isFinite(requestedCapacity) && requestedCapacity > MAX_LIST_SIZE) ||
568+
(Number.isFinite(requestedOrigin) && requestedOrigin < -MAX_LIST_SIZE) ||
569+
(Number.isFinite(requestedCapacity) &&
570+
Number.isFinite(requestedOrigin) &&
571+
requestedCapacity - requestedOrigin > MAX_LIST_SIZE)
572+
) {
573+
throw new RangeError(
574+
'Invalid List size: a List cannot hold more than ' +
575+
MAX_LIST_SIZE +
576+
' (2 ** 30) values.'
577+
);
578+
}
579+
}
580+
552581
function setListBounds(list, begin, end) {
582+
// Validate full-precision bounds before int32 coercion.
583+
validateListBoundsRequest(list, begin, end);
584+
553585
// Sanitize begin & end using this shorthand for ToInt32(argument)
554586
// http://www.ecma-international.org/ecma-262/6.0/#sec-toint32
555587
if (begin !== undefined) {
@@ -588,7 +620,8 @@ function setListBounds(list, begin, end) {
588620
owner
589621
);
590622
newLevel += SHIFT;
591-
offsetShift += 1 << newLevel;
623+
// Shift origin into non-negative space as trie height grows.
624+
offsetShift += levelCapacity(newLevel);
592625
}
593626
if (offsetShift) {
594627
newOrigin += offsetShift;
@@ -601,7 +634,7 @@ function setListBounds(list, begin, end) {
601634
const newTailOffset = getTailOffset(newCapacity);
602635

603636
// New size might need creating a higher root.
604-
while (newTailOffset >= 1 << (newLevel + SHIFT)) {
637+
while (newTailOffset >= levelCapacity(newLevel + SHIFT)) {
605638
newRoot = new VNode(
606639
newRoot && newRoot.array.length ? [newRoot] : [],
607640
owner
@@ -698,3 +731,16 @@ function setListBounds(list, begin, end) {
698731
function getTailOffset(size) {
699732
return size < SIZE ? 0 : ((size - 1) >>> SHIFT) << SHIFT;
700733
}
734+
735+
// The largest number of values a List can hold. Above this the 32-bit trie math
736+
// in setListBounds() stays in the safe signed 32-bit range.
737+
const MAX_LIST_SIZE = 2 ** 30; // 1073741824
738+
739+
/**
740+
* Computes 2 ** exp for the trie level-raising loops in setListBounds().
741+
* Use the cheap bitwise operator shift whenever possible, otherwise fall back to exponentiation.
742+
* This is necessary because bitwise operators in JavaScript only work on 32-bit signed integers, so for exp >= 31, we need to use exponentiation to avoid overflow.
743+
*/
744+
function levelCapacity(exp) {
745+
return exp < 31 ? 1 << exp : 2 ** exp;
746+
}

0 commit comments

Comments
 (0)