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

(coll) LinkedList has incorrect implementation comment

    XMLWordPrintable

    Details

    • Type: Bug
    • Status: Closed
    • Priority: P2
    • Resolution: Fixed
    • Affects Version/s: 7, 9
    • Fix Version/s: 9
    • Component/s: core-libs
    • Subcomponent:
    • Resolved In Build:
      b72
    • CPU:
      generic
    • OS:
      generic
    • Verification:
      Verified

      Backports

        Description

        FULL PRODUCT VERSION :
        java version "1.7.0_04"
        Java(TM) SE Runtime Environment (build 1.7.0_04-b22)
        Java HotSpot(TM) 64-Bit Server VM (build 23.0-b21, mixed mode)

        ADDITIONAL OS VERSION INFORMATION :
        ver Windows 7 Ultimate 64-bit Service Pack 1

        EXTRA RELEVANT SYSTEM CONFIGURATION :
        Not relevant

        A DESCRIPTION OF THE PROBLEM :
        The bug concerns the documentation in LinkedList.java. A false invariant is declared that can be broken at any time and thus makes it variant.
        /**
             * Pointer to first node.
             * Invariant: (first == null && last == null) ||
             * (first.prev == null && first.item != null)
             */
            transient Node<E> first;

            /**
             * Pointer to last node.
             * Invariant: (first == null && last == null) ||
             * (last.next == null && last.item != null)
             */
            transient Node<E> last;

        These two invariants predicate that either the node first and the node last is null which is the case whenever there is no element in it, or, "last" has no successor and "first" has no predecessor as well as their items might not be null.

        Reading this, one will think LinkedList does not allow null elements. However, it does. By adding a null element to the LinkedList, this invariant indeed returns false, thus making it not an invariant.

        REGRESSION. Last worked in version 6u31

        STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
        You can reproduce this at any given time by creating a LinkedList with no elements and adding null to it.

        EXPECTED VERSUS ACTUAL BEHAVIOR :
        EXPECTED -
        An expected result would be that either the invariant not be there or LinkedList not allow null elements.
        ACTUAL -
        The invariant is stated and one can add null Elements

        ERROR MESSAGES/STACK TRACES THAT OCCUR :
        No error messages.

        REPRODUCIBILITY :
        This bug can be reproduced always.

        ---------- BEGIN SOURCE ----------
        *** BEGIN SOURCE ***
        import java.util.List;
        import java.util.LinkedList;

        public class FalseInvariant {

        public static void main(String... args) {
        List<Object> list = new LinkedList<>(); // (first == null && last == null) == true
        list.add(null); // (first == null && last == null) == false, first.prev == null == true, first.item != null == false, true && false == false, false || false == false, invariant == false (same goes with last)
        System.exit(0);
        }
        }
        *** END SOURCE ***
        ---------- END SOURCE ----------

        CUSTOMER SUBMITTED WORKAROUND :
        A workaround to this bug would be to ignore it.

          Attachments

            Issue Links

              Activity

                People

                Assignee:
                martin Martin Buchholz
                Reporter:
                igerasim Ivan Gerasimov
                Votes:
                0 Vote for this issue
                Watchers:
                5 Start watching this issue

                  Dates

                  Created:
                  Updated:
                  Resolved:
                  Imported: