Skip to content

Commit c0a8a1e

Browse files
wozhenbang2004Google Java Core Libraries
authored andcommitted
Fix rotating by Integer.MIN_VALUE.
The primitive array `rotate` methods negate the distance before reducing it modulo the range length. Negating `Integer.MIN_VALUE` overflows, so rotating `{1, 2, 3}` by that distance produces `{2, 3, 1}` instead of `{3, 1, 2}`, unlike the documented `Collections.rotate` equivalent. Fixes #8807 RELNOTES=n/a PiperOrigin-RevId: 1010956879
1 parent efae76a commit c0a8a1e

32 files changed

Lines changed: 198 additions & 112 deletions

‎android/guava-tests/test/com/google/common/primitives/BooleansTest.java‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -342,6 +342,17 @@ public void testRotate_multiElementArray() {
342342
new boolean[] {true, true, false, true, false});
343343
}
344344

345+
public void testRotate_minValueDistance() {
346+
testRotate(
347+
new boolean[] {true, false, false}, Integer.MIN_VALUE, new boolean[] {false, true, false});
348+
testRotate(
349+
new boolean[] {false, true, false, false, true},
350+
Integer.MIN_VALUE,
351+
1,
352+
4,
353+
new boolean[] {false, false, true, false, true});
354+
}
355+
345356
public void testRotateIndexed_emptyRange() {
346357
boolean[] empty = {};
347358
boolean[] expectedEmpty = {};

‎android/guava-tests/test/com/google/common/primitives/BytesTest.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -367,6 +367,11 @@ public void testRotate_multiElementArray() {
367367
testRotate(new byte[] {1, 2, 3, 4, 5}, 6, new byte[] {5, 1, 2, 3, 4});
368368
}
369369

370+
public void testRotate_minValueDistance() {
371+
testRotate(new byte[] {1, 2, 3}, Integer.MIN_VALUE, new byte[] {3, 1, 2});
372+
testRotate(new byte[] {0, 1, 2, 3, 4}, Integer.MIN_VALUE, 1, 4, new byte[] {0, 3, 1, 2, 4});
373+
}
374+
370375
public void testRotateIndexed_emptyRange() {
371376
byte[] empty = {};
372377
byte[] expectedEmpty = {};

‎android/guava-tests/test/com/google/common/primitives/CharsTest.java‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -435,6 +435,16 @@ public void testRotate_multiElementArray() {
435435
testRotate(new char[] {'1', '2', '3', '4', '5'}, 6, new char[] {'5', '1', '2', '3', '4'});
436436
}
437437

438+
public void testRotate_minValueDistance() {
439+
testRotate(new char[] {'1', '2', '3'}, Integer.MIN_VALUE, new char[] {'3', '1', '2'});
440+
testRotate(
441+
new char[] {'0', '1', '2', '3', '4'},
442+
Integer.MIN_VALUE,
443+
1,
444+
4,
445+
new char[] {'0', '3', '1', '2', '4'});
446+
}
447+
438448
public void testRotateIndexed_emptyRange() {
439449
char[] empty = {};
440450
char[] expectedEmpty = {};

‎android/guava-tests/test/com/google/common/primitives/DoublesTest.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -432,6 +432,11 @@ public void testRotate_multiElementArray() {
432432
testRotate(new double[] {1, 2, 3, 4, 5}, 6, new double[] {5, 1, 2, 3, 4});
433433
}
434434

435+
public void testRotate_minValueDistance() {
436+
testRotate(new double[] {1, 2, 3}, Integer.MIN_VALUE, new double[] {3, 1, 2});
437+
testRotate(new double[] {0, 1, 2, 3, 4}, Integer.MIN_VALUE, 1, 4, new double[] {0, 3, 1, 2, 4});
438+
}
439+
435440
public void testRotateIndexed_emptyRange() {
436441
double[] empty = {};
437442
double[] expectedEmpty = {};

‎android/guava-tests/test/com/google/common/primitives/FloatsTest.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -425,6 +425,11 @@ public void testRotate_multiElementArray() {
425425
testRotate(new float[] {1, 2, 3, 4, 5}, 6, new float[] {5, 1, 2, 3, 4});
426426
}
427427

428+
public void testRotate_minValueDistance() {
429+
testRotate(new float[] {1, 2, 3}, Integer.MIN_VALUE, new float[] {3, 1, 2});
430+
testRotate(new float[] {0, 1, 2, 3, 4}, Integer.MIN_VALUE, 1, 4, new float[] {0, 3, 1, 2, 4});
431+
}
432+
428433
public void testRotateIndexed_emptyRange() {
429434
float[] empty = {};
430435
float[] expectedEmpty = {};

‎android/guava-tests/test/com/google/common/primitives/IntsTest.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -425,6 +425,11 @@ public void testRotate_multiElementArray() {
425425
testRotate(new int[] {1, 2, 3, 4, 5}, 6, new int[] {5, 1, 2, 3, 4});
426426
}
427427

428+
public void testRotate_minValueDistance() {
429+
testRotate(new int[] {1, 2, 3}, Integer.MIN_VALUE, new int[] {3, 1, 2});
430+
testRotate(new int[] {0, 1, 2, 3, 4}, Integer.MIN_VALUE, 1, 4, new int[] {0, 3, 1, 2, 4});
431+
}
432+
428433
public void testRotateIndexed_emptyRange() {
429434
int[] empty = {};
430435
int[] expectedEmpty = {};

‎android/guava-tests/test/com/google/common/primitives/LongsTest.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -418,6 +418,11 @@ public void testRotate_multiElementArray() {
418418
testRotate(new long[] {1, 2, 3, 4, 5}, 6, new long[] {5, 1, 2, 3, 4});
419419
}
420420

421+
public void testRotate_minValueDistance() {
422+
testRotate(new long[] {1, 2, 3}, Integer.MIN_VALUE, new long[] {3, 1, 2});
423+
testRotate(new long[] {0, 1, 2, 3, 4}, Integer.MIN_VALUE, 1, 4, new long[] {0, 3, 1, 2, 4});
424+
}
425+
421426
public void testRotateIndexed_emptyRange() {
422427
long[] empty = {};
423428
long[] expectedEmpty = {};

‎android/guava-tests/test/com/google/common/primitives/ShortsTest.java‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -448,6 +448,11 @@ public void testRotate_multiElementArray() {
448448
testRotate(new short[] {1, 2, 3, 4, 5}, 6, new short[] {5, 1, 2, 3, 4});
449449
}
450450

451+
public void testRotate_minValueDistance() {
452+
testRotate(new short[] {1, 2, 3}, Integer.MIN_VALUE, new short[] {3, 1, 2});
453+
testRotate(new short[] {0, 1, 2, 3, 4}, Integer.MIN_VALUE, 1, 4, new short[] {0, 3, 1, 2, 4});
454+
}
455+
451456
public void testRotateIndexed_emptyRange() {
452457
short[] empty = {};
453458
short[] expectedEmpty = {};

‎android/guava/src/com/google/common/primitives/Booleans.java‎

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818
import static com.google.common.base.Preconditions.checkElementIndex;
1919
import static com.google.common.base.Preconditions.checkNotNull;
2020
import static com.google.common.base.Preconditions.checkPositionIndexes;
21+
import static java.lang.Math.floorMod;
2122
import static java.lang.System.arraycopy;
2223
import static java.util.Collections.emptyList;
2324

@@ -598,15 +599,13 @@ public static void rotate(boolean[] array, int distance, int fromIndex, int toIn
598599
return;
599600
}
600601

601-
// Obtain m = (-distance mod length), a non-negative value less than "length". This is how many
602-
// places left to rotate.
603-
int m = -distance % length;
604-
m = (m < 0) ? m + length : m;
605-
// The current index of what will become the first element of the rotated section.
606-
int newFirstIndex = m + fromIndex;
607-
if (newFirstIndex == fromIndex) {
602+
// Map the given distance to an equivalent, non-negative value less than "length".
603+
distance = floorMod(distance, length);
604+
if (distance == 0) {
608605
return;
609606
}
607+
// The current index of what will become the first element of the rotated section.
608+
int newFirstIndex = toIndex - distance;
610609

611610
reverse(array, fromIndex, newFirstIndex);
612611
reverse(array, newFirstIndex, toIndex);

‎android/guava/src/com/google/common/primitives/Bytes.java‎

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,7 @@
1818
import static com.google.common.base.Preconditions.checkElementIndex;
1919
import static com.google.common.base.Preconditions.checkNotNull;
2020
import static com.google.common.base.Preconditions.checkPositionIndexes;
21+
import static java.lang.Math.floorMod;
2122
import static java.lang.System.arraycopy;
2223
import static java.util.Collections.emptyList;
2324

@@ -448,15 +449,13 @@ public static void rotate(byte[] array, int distance, int fromIndex, int toIndex
448449
return;
449450
}
450451

451-
// Obtain m = (-distance mod length), a non-negative value less than "length". This is how many
452-
// places left to rotate.
453-
int m = -distance % length;
454-
m = (m < 0) ? m + length : m;
455-
// The current index of what will become the first element of the rotated section.
456-
int newFirstIndex = m + fromIndex;
457-
if (newFirstIndex == fromIndex) {
452+
// Map the given distance to an equivalent, non-negative value less than "length".
453+
distance = floorMod(distance, length);
454+
if (distance == 0) {
458455
return;
459456
}
457+
// The current index of what will become the first element of the rotated section.
458+
int newFirstIndex = toIndex - distance;
460459

461460
reverse(array, fromIndex, newFirstIndex);
462461
reverse(array, newFirstIndex, toIndex);

0 commit comments

Comments
 (0)