Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-8076442

Cannot fully read BitSet.stream() if bit Integer.MAX_VALUE is set

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: P4
    • Resolution: Fixed
    • Affects Version/s: 8, 8u40, 9
    • Fix Version/s: 9
    • Component/s: core-libs
    • Labels:
    • Subcomponent:
    • Resolved In Build:
      b60
    • Verification:
      Verified

      Backports

        Description

        FULL PRODUCT VERSION :
        java version "1.8.0_40"
        Java(TM) SE Runtime Environment (build 1.8.0_40-b27)
        Java HotSpot(TM) 64-Bit Server VM (build 25.40-b25, mixed mode)


        ADDITIONAL OS VERSION INFORMATION :
        Darwin Kernel Version 13.4.0

        A DESCRIPTION OF THE PROBLEM :
        If the last bit (Integer.MAX_VALUE) in a BitSet is set, all attempts to fully read the stream returned by BitSet.stream() throw an IndexOutOfBoundsException.

        The cause is line 1232 in BitSet.java:

        next = nextSetBit(next+1)

        If next is Integer.MAX_VALUE, next+1 overflows to Integer.MIN_VALUE, and nextSetBit() throws an IndexOutOfBoundsException.

        The bug is also present in the current JDK 9 sources: http://hg.openjdk.java.net/jdk9/dev/jdk/file/a54a0169968c/src/java.base/share/classes/java/util/BitSet.java#l1232

        Replacing line 1232 by

        next = next == Integer.MAX_VALUE ? -1 : nextSetBit(next+1);

        should fix this.

        (By the way, this is not just a theoretical possibility. It happened in real life - I ran into it while using BitSet for a prime number sieve. Integer.MAX_VALUE is a prime number, so the bit was set.)

        STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
        BitSet b = new BitSet();
        b.set(Integer.MAX_VALUE);
        b.stream().count(); // throws IndexOutOfBoundsException (as many other stream methods)

        EXPECTED VERSUS ACTUAL BEHAVIOR :
        EXPECTED -
        b.stream().count() should return 1 (similar for other stream methods)
        ACTUAL -
        b.stream().count() throws IndexOutOfBoundsException

        ERROR MESSAGES/STACK TRACES THAT OCCUR :
        Exception in thread "main" java.lang.IndexOutOfBoundsException: fromIndex < 0: -2147483648
        at java.util.BitSet.nextSetBit(BitSet.java:712)
        at java.util.BitSet$1BitSetIterator.nextInt(BitSet.java:1232)
        at java.util.PrimitiveIterator$OfInt.forEachRemaining(PrimitiveIterator.java:115)
        at java.util.Spliterators$IntIteratorSpliterator.forEachRemaining(Spliterators.java:1908)
        at java.util.Spliterator$OfInt.forEachRemaining(Spliterator.java:693)
        at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:512)
        at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:502)
        at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708)
        at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
        at java.util.stream.LongPipeline.reduce(LongPipeline.java:438)
        at java.util.stream.LongPipeline.sum(LongPipeline.java:396)
        at java.util.stream.IntPipeline.count(IntPipeline.java:429)
        at BitSetBug.main(BitSetBug.java:7)


        REPRODUCIBILITY :
        This bug can be reproduced always.

        ---------- BEGIN SOURCE ----------
        import java.util.BitSet;

        public class BitSetBug {
          public static void main(String[] args) {
            BitSet b = new BitSet();
            b.set(Integer.MAX_VALUE);
            b.stream().count(); // throws IndexOutOfBoundsException
          }
        }
        ---------- END SOURCE ----------

          Attachments

            Issue Links

              Activity

                People

                Assignee:
                chegar Chris Hegarty
                Reporter:
                webbuggrp Webbug Group
                Votes:
                0 Vote for this issue
                Watchers:
                4 Start watching this issue

                  Dates

                  Created:
                  Updated:
                  Resolved: