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

Accessing a nested sublist leads to StackOverflowError

    XMLWordPrintable

    Details

      Description

      FULL PRODUCT VERSION :
      java version "1.7.0_71"
      Java(TM) SE Runtime Environment (build 1.7.0_71-b14)
      Java HotSpot(TM) 64-Bit Server VM (build 24.71-b01, mixed mode)


      ADDITIONAL OS VERSION INFORMATION :
      Darwin MacBook-Pro.local 14.1.0 Darwin Kernel Version 14.1.0: Thu Feb 26 19:26:47 PST 2015; root:xnu-2782.10.73~1/RELEASE_X86_64 x86_64

      But this is an OS agnostic bug: in Java code.

      A DESCRIPTION OF THE PROBLEM :
      Invoking List.subList(..) on a typical List implementation in java.util, returns a view onto the parent list. If you then invoke subList on that returned view, what you get is a view of view onto the parent list. Logically, this is the correct behavior. Implementation-wise, however, this "second-order" view is a [n unnecessary] wrapper on top of a wrapper of the parent list. Unfortunately, this small inefficiency can quickly snowball if an algorithm repeatedly applies subList starting with a good sized list (say 500k items). In the extreme cases, you end up with list instances which blow up (StackOverflowError) on later invoking List.get(int).

      STEPS TO FOLLOW TO REPRODUCE THE PROBLEM :
      See attached unit test

      EXPECTED VERSUS ACTUAL BEHAVIOR :
      EXPECTED -
      Unit test should pass.
      ACTUAL -
      Unit test fails:

      [java.util.Arrays$ArrayList, size:50,000] 2,704 ms

      java.lang.AssertionError: [java.util.Arrays$ArrayList, size:50,000]: error on 29,590th sub-list - java.lang.StackOverflowError
      at org.junit.Assert.fail(Assert.java:88)
      at com.gnahraf.util.bf.SubListBugReport.assertSubListTraversal(SubListBugReport.java:65)
      at com.gnahraf.util.bf.SubListBugReport.assertSubListTraversal(SubListBugReport.java:43)
      at com.gnahraf.util.bf.SubListBugReport.showIt(SubListBugReport.java:35)
      at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
      at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
      at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
      at org.junit.runners.model.FrameworkMethod$1.runReflectiveCall(FrameworkMethod.java:50)
      at org.junit.internal.runners.model.ReflectiveCallable.run(ReflectiveCallable.java:12)
      at org.junit.runners.model.FrameworkMethod.invokeExplosively(FrameworkMethod.java:47)
      at org.junit.internal.runners.statements.InvokeMethod.evaluate(InvokeMethod.java:17)
      at org.junit.runners.ParentRunner.runLeaf(ParentRunner.java:325)
      at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:78)
      at org.junit.runners.BlockJUnit4ClassRunner.runChild(BlockJUnit4ClassRunner.java:57)
      at org.junit.runners.ParentRunner$3.run(ParentRunner.java:290)
      at org.junit.runners.ParentRunner$1.schedule(ParentRunner.java:71)
      at org.junit.runners.ParentRunner.runChildren(ParentRunner.java:288)
      at org.junit.runners.ParentRunner.access$000(ParentRunner.java:58)
      at org.junit.runners.ParentRunner$2.evaluate(ParentRunner.java:268)
      at org.junit.runners.ParentRunner.run(ParentRunner.java:363)
      at org.junit.runner.JUnitCore.run(JUnitCore.java:137)
      at com.intellij.junit4.JUnit4IdeaTestRunner.startRunnerWithArgs(JUnit4IdeaTestRunner.java:74)
      at com.intellij.rt.execution.junit.JUnitStarter.prepareStreamsAndStart(JUnitStarter.java:211)
      at com.intellij.rt.execution.junit.JUnitStarter.main(JUnitStarter.java:67)
      at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
      at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57)
      at com.intellij.rt.execution.application.AppMain.main(AppMain.java:134)

      [java.util.Arrays$ArrayList, size:500] 0 ms

      REPRODUCIBILITY :
      This bug can be reproduced always.

      ---------- BEGIN SOURCE ----------
      /*
       * Copyright (c) 2015 Babak Farhang
       */

      package com.gnahraf.util.bf;


      import org.junit.Test;


      import java.text.DecimalFormat;
      import java.util.Arrays;
      import java.util.List;

      import static org.junit.Assert.*;

      /**
       * Created by babak on 4/29/15.
       */
      public class SubListBugReport {

          DecimalFormat formatter = new DecimalFormat("#,###");


          @Test
          public void worksForSmall() {
              assertSubListTraversal(500);
          }


          @Test
          public void showIt() {
              assertSubListTraversal(50000);
          }


          void assertSubListTraversal(int count) {
              Integer[] array = new Integer[count];
              for (int i = 0; i < count; ++i)
                  array[i] = i;
              assertSubListTraversal(Arrays.asList(array));
          }


          void assertSubListTraversal(List<?> list) {
              int i = 1;
              StackOverflowError error = null;
              long tick = System.currentTimeMillis();
              try {
                  List<?> sub = list;
                  for (; i < list.size(); ) {
                      sub = sub.subList(1, sub.size());
                      assertEquals(list.get(i++), sub.get(0));
                  }
                  assertEquals(1, sub.size());
              } catch (StackOverflowError soe) {
                  error = soe;
              }

              long lap = System.currentTimeMillis() - tick;
              System.out.println(label(list) + " " + formatter.format(lap) + " ms");
              if (error != null) {
                  fail(label(list) + ": error on " + formatter.format(i) + "th sub-list - " + error);
                  throw error;
              }
          }

          private void printLap(String label, long tick) {
              long lap = System.currentTimeMillis() - tick;
              System.out.println("[" + label + "] " + formatter.format(lap) + " ms");
          }

          private String label(List<?> list) {
              return "[" + list.getClass().getName() + ", size:" + formatter.format(list.size()) + "]";
          }
      }

      ---------- END SOURCE ----------

      CUSTOMER SUBMITTED WORKAROUND :
      /*
       * Copyright (c) 2015 Babak Farhang.
       * Licensed under the Apache License, Version 2.0
       */

      package com.gnahraf.util.bf;

      import java.util.AbstractList;
      import java.util.Collections;
      import java.util.List;

      /**
       * Wrap instances with this class as a work-around.
       * Created by babak on 4/29/15.
       */
      public class SubList<T> extends AbstractList<T> {

          private final static SubList<?> EMPTY = new SubList<Object>(Collections.EMPTY_LIST);

          public static <T> SubList<T> empty() {
              return (SubList<T>) EMPTY;
          }

          private final List<T> base;
          private final int offset;
          private final int size;

          public SubList(List<T> base) {
              this(base, 0, base.size(), false);
          }

          public SubList(List<T> base, int offset, int size) {
              this(base, offset, size, false);
              if (base == null)
                  throw new IllegalArgumentException("null base list");
              if (offset < 0)
                  throw new IllegalArgumentException("offset: " + offset);
              if (size < 0)
                  throw new IllegalArgumentException("size: " + offset);
              if (offset + size > base.size())
                  throw new IllegalArgumentException(
                          "offset: " + offset + ", size: " + size + "; base.size(): " + base.size());
          }


          private SubList(List<T> base, int offset, int size, boolean ignore) {
              this.base = base;
              this.offset = offset;
              this.size = size;
          }

          @Override
          public T get(int location) {
              return base.get(location + offset);
          }

          @Override
          public int size() {
              return size;
          }

          @Override
          public List<T> subList(int start, int end) {
              if (end == size && start == 0)
                  return this;

              if (start < 0 || end < start || end > size)
                  throw new IllegalArgumentException(
                          "start: " + start + ", end: " + end + ", size: " + size);

              int subSize = end - start;
              if (subSize == 0)
                  return empty();
              else
                  return new SubList<T>(base, offset + start, subSize, false);
          }
      }


        Attachments

          Issue Links

            Activity

              People

              Assignee:
              igerasim Ivan Gerasimov
              Reporter:
              webbuggrp Webbug Group
              Votes:
              0 Vote for this issue
              Watchers:
              8 Start watching this issue

                Dates

                Created:
                Updated:
                Resolved: