In XWiki Platform, saving a document with a large object number leads to persistent OOM errors

@@ -102,7 +102,7 @@ public void add(int index, BaseObject element)
         // Check if the index is valid
         rangeCheckForAdd(index);
 
-        // Move right values
+        // Shifts right values to the right
         if (index < this.size) {
             for (int i = this.size - 1; i >= index; --i) {
                 put(i + 1, get(i));
@@ -128,7 +128,26 @@ public BaseObject remove(int index)
     {
         rangeCheck(index);
 
-        return this.map.remove(index);
+        BaseObject previous = this.map.remove(index);
+
+        // Shifts right values to the left
+        if (index < this.size - 1) {
+            for (int i = index; i < this.size - 1; ++i) {
+                put(i, get(i + 1));
+            }
+        }
+
+        // The list is one element shorter
+        --this.size;
+
+        return previous;
+    }
+
+    @Override
+    public void clear()
+    {
+        this.map.clear();
+        this.size = 0;
     }
 
     private void rangeCheck(int index)

@@ -120,12 +120,26 @@ void remove()
         assertEquals(3, objects.size());
 
         objects.remove(0);
-        objects.remove(2);
 
-        assertNull(objects.get(0));
-        assertSame(XOBJ2, objects.get(1));
-        assertNull(objects.get(2));
+        assertEquals(2, objects.size());
+        assertSame(XOBJ2, objects.get(0));
+        assertSame(XOBJ3, objects.get(1));
+
+        objects.remove(1);
+
+        assertEquals(1, objects.size());
+        assertSame(XOBJ2, objects.get(0));
+    }
+
+    @Test
+    void clear()
+    {
+        BaseObjects objects = new BaseObjects(Arrays.asList(XOBJ1, XOBJ2, XOBJ3));
 
         assertEquals(3, objects.size());
+
+        objects.clear();
+
+        assertEquals(0, objects.size());
     }
 }

@@ -610,6 +610,7 @@
     <dependency>
       <groupId>com.google.guava</groupId>
       <artifactId>guava-testlib</artifactId>
+      <scope>test</scope>
     </dependency>
 
     <dependency>

@@ -607,6 +607,10 @@
       <version>1.6</version>
       <scope>test</scope>
     </dependency>
+    <dependency>
+      <groupId>com.google.guava</groupId>
+      <artifactId>guava-testlib</artifactId>
+    </dependency>
 
     <dependency>
       <groupId>org.xwiki.commons</groupId>

@@ -49,6 +49,7 @@
 import java.util.SortedMap;
 import java.util.TreeMap;
 import java.util.Vector;
+import java.util.concurrent.ConcurrentSkipListMap;
 import java.util.regex.Matcher;
 import java.util.regex.Pattern;
 import java.util.zip.ZipEntry;
@@ -167,6 +168,7 @@
 import com.xpn.xwiki.doc.merge.MergeResult;
 import com.xpn.xwiki.doc.rcs.XWikiRCSNodeInfo;
 import com.xpn.xwiki.internal.cache.rendering.RenderingCache;
+import com.xpn.xwiki.internal.doc.BaseObjects;
 import com.xpn.xwiki.internal.doc.XWikiAttachmentList;
 import com.xpn.xwiki.internal.filter.XWikiDocumentFilterUtils;
 import com.xpn.xwiki.internal.render.OldRendering;
@@ -504,10 +506,10 @@ private static LinkParser getLinkParser() {
 
     /**
      * Map holding document objects indexed by XClass references (i.e. Document References since a XClass reference
-     * points to a document). The map is not synchronized, and uses a TreeMap implementation to preserve index ordering
-     * (consistent sorted order for output to XML, rendering in velocity, etc.)
+     * points to a document). The preserve index ordering (consistent sorted order for output to XML, rendering in
+     * velocity, etc.)
      */
-    private Map<DocumentReference, List<BaseObject>> xObjects = new TreeMap<DocumentReference, List<BaseObject>>();
+    private Map<DocumentReference, BaseObjects> xObjects = new ConcurrentSkipListMap<>();
 
     private final XWikiAttachmentList attachmentList = new XWikiAttachmentList(XWikiDocument.this);
 
@@ -2544,7 +2546,7 @@ public void setXClass(BaseClass xwikiClass)
      */
     public Map<DocumentReference, List<BaseObject>> getXObjects()
     {
-        return this.xObjects;
+        return (Map) this.xObjects;
     }
 
     /**
@@ -2572,7 +2574,9 @@ public void setXObjects(Map<DocumentReference, List<BaseObject>> objects)
         }
 
         // Replace the current objects with the provided ones.
-        this.xObjects = objects;
+        Map<DocumentReference, BaseObjects> objectsCopy = new ConcurrentSkipListMap<>();
+        objects.forEach((k, v) -> objectsCopy.put(k, new BaseObjects(v)));
+        this.xObjects = objectsCopy;
     }
 
     /**
@@ -2636,9 +2640,9 @@ public int createXObject(EntityReference classReference, XWikiContext context) t
         BaseObject object = BaseClass.newCustomClassInstance(absoluteClassReference, context);
         object.setOwnerDocument(this);
         object.setXClassReference(classReference);
-        List<BaseObject> objects = this.xObjects.get(absoluteClassReference);
+        BaseObjects objects = this.xObjects.get(absoluteClassReference);
         if (objects == null) {
-            objects = new ArrayList<BaseObject>();
+            objects = new BaseObjects();
             this.xObjects.put(absoluteClassReference, objects);
         }
         objects.add(object);
@@ -2758,16 +2762,7 @@ public void setXObjects(DocumentReference classReference, List<BaseObject> objec
         }
 
         // Add new objects
-        if (objects.isEmpty()) {
-            // Pretty wrong but can't remove that for retro compatibility reasons...
-            // Note that it means that someone can put an unmodifiable list here make impossible to add any object of
-            // this class.
-            this.xObjects.put(classReference, objects);
-        } else {
-            for (BaseObject baseObject : objects) {
-                addXObject(classReference, baseObject);
-            }
-        }
+        this.xObjects.put(classReference, new BaseObjects(objects));
 
         setMetaDataDirty(true);
     }
@@ -3062,9 +3057,9 @@ public void setXObject(DocumentReference classReference, int nb, BaseObject obje
             object.setNumber(nb);
         }
 
-        List<BaseObject> objects = this.xObjects.get(classReference);
+        BaseObjects objects = this.xObjects.get(classReference);
         if (objects == null) {
-            objects = new ArrayList<BaseObject>();
+            objects = new BaseObjects();
             this.xObjects.put(classReference, objects);
         }
         while (nb >= objects.size()) {
@@ -3088,9 +3083,9 @@ public void setXObject(int nb, BaseObject object)
         object.setOwnerDocument(this);
         object.setNumber(nb);
 
-        List<BaseObject> objects = this.xObjects.get(object.getXClassReference());
+        BaseObjects objects = this.xObjects.get(object.getXClassReference());
         if (objects == null) {
-            objects = new ArrayList<BaseObject>();
+            objects = new BaseObjects();
             this.xObjects.put(object.getXClassReference(), objects);
         }
         while (nb >= objects.size()) {

@@ -0,0 +1,152 @@
+/*
+ * See the NOTICE file distributed with this work for additional
+ * information regarding copyright ownership.
+ *
+ * This is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * This software is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this software; if not, write to the Free
+ * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
+ * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
+ */
+package com.xpn.xwiki.internal.doc;
+
+import java.util.AbstractList;
+import java.util.Collection;
+import java.util.Map;
+import java.util.concurrent.ConcurrentSkipListMap;
+
+import com.xpn.xwiki.objects.BaseObject;
+
+/**
+ * Implement a list of {@link BaseObject} as seen by a document (meaning that the list index matched the object number)
+ * using a {@link Map} storage to avoid wasting memory with null entries.
+ * 
+ * @version $Id$
+ * @since 14.0RC1
+ */
+// TODO: expose APIs to navigate non null objects directly instead of going through each entry and skipping explicitly
+// null ones
+public class BaseObjects extends AbstractList<BaseObject>
+{
+    // Sort keys so that it's possible to navigate non null entries without going through them all
+    private Map<Integer, BaseObject> map = new ConcurrentSkipListMap<>();
+
+    private int size;
+
+    /**
+     * Constructs an empty list.
+     */
+    public BaseObjects()
+    {
+
+    }
+
+    /**
+     * Constructs a list containing the elements of the specified collection, in the order they are returned by the
+     * collection's iterator.
+     * 
+     * @param collection the collection to copy
+     */
+    public BaseObjects(Collection<BaseObject> collection)
+    {
+        collection.forEach(this::add);
+    }
+
+    @Override
+    public BaseObject get(int index)
+    {
+        rangeCheck(index);
+
+        return this.map.get(index);
+    }
+
+    @Override
+    public int size()
+    {
+        return this.size;
+    }
+
+    private BaseObject put(int index, BaseObject element)
+    {
+        BaseObject old;
+        if (element == null) {
+            // We don't want to keep null values in memory
+            old = this.map.remove(index);
+        } else {
+            // Make sure the object number is right
+            element.setNumber(index);
+
+            old = this.map.put(index, element);
+        }
+
+        // Increment size if needed
+        if (this.size <= index) {
+            this.size = index + 1;
+        }
+
+        return old;
+    }
+
+    @Override
+    public void add(int index, BaseObject element)
+    {
+        // Check if the index is valid
+        rangeCheckForAdd(index);
+
+        // Move right values
+        if (index < this.size) {
+            for (int i = this.size - 1; i >= index; --i) {
+                put(i + 1, get(i));
+            }
+        }
+
+        // Insert new value
+        put(index, element);
+    }
+
+    @Override
+    public BaseObject set(int index, BaseObject element)
+    {
+        // Check if the index is valid
+        rangeCheck(index);
+
+        // Set the value and remember the old one
+        return put(index, element);
+    }
+
+    @Override
+    public BaseObject remove(int index)
+    {
+        rangeCheck(index);
+
+        return this.map.remove(index);
+    }
+
+    private void rangeCheck(int index)
+    {
+        if (index < 0 || index >= this.size) {
+            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+        }
+    }
+
+    private void rangeCheckForAdd(int index)
+    {
+        if (index < 0 || index > this.size || index == Integer.MAX_VALUE) {
+            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
+        }
+    }
+
+    private String outOfBoundsMsg(int index)
+    {
+        return "Index: " + index + ", Size: " + size;
+    }
+}

@@ -0,0 +1,131 @@
+/*
+ * See the NOTICE file distributed with this work for additional
+ * information regarding copyright ownership.
+ *
+ * This is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU Lesser General Public License as
+ * published by the Free Software Foundation; either version 2.1 of
+ * the License, or (at your option) any later version.
+ *
+ * This software is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with this software; if not, write to the Free
+ * Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
+ * 02110-1301 USA, or see the FSF site: http://www.fsf.org.
+ */
+package com.xpn.xwiki.internal.doc;
+
+import java.util.Arrays;
+
+import org.junit.jupiter.api.Test;
+
+import com.xpn.xwiki.objects.BaseObject;
+
+import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.junit.jupiter.api.Assertions.assertNull;
+import static org.junit.jupiter.api.Assertions.assertSame;
+import static org.junit.jupiter.api.Assertions.assertThrows;
+
+/**
+ * Validate {@link BaseObjects}.
+ * 
+ * @version $Id$
+ */
+public class BaseObjectsTest
+{
+    private static class TestBaseObject extends BaseObject
+    {
+        @Override
+        public String toString()
+        {
+            return String.valueOf(getNumber());
+        }
+    }
+
+    private static final BaseObject XOBJ1 = new TestBaseObject();
+
+    private static final BaseObject XOBJ2 = new TestBaseObject();
+
+    private static final BaseObject XOBJ3 = new TestBaseObject();
+
+    private static final BaseObject XOBJ4 = new TestBaseObject();
+
+    @Test
+    void add()
+    {
+        BaseObjects objects = new BaseObjects();
+
+        assertEquals(0, objects.size());
+
+        objects.add(XOBJ1);
+
+        assertEquals(1, objects.size());
+
+        objects.add(null);
+
+        assertEquals(2, objects.size());
+
+        objects.add(XOBJ2);
+
+        assertEquals(3, objects.size());
+        assertSame(XOBJ1, objects.get(0));
+        assertEquals(0, objects.get(0).getNumber());
+        assertNull(objects.get(1));
+        assertSame(XOBJ2, objects.get(2));
+        assertEquals(2, objects.get(2).getNumber());
+
+        objects.add(1, XOBJ3);
+
+        assertEquals(4, objects.size());
+        assertSame(XOBJ1, objects.get(0));
+        assertEquals(0, objects.get(0).getNumber());
+        assertSame(XOBJ3, objects.get(1));
+        assertEquals(1, objects.get(1).getNumber());
+        assertNull(objects.get(2));
+        assertSame(XOBJ2, objects.get(3));
+        assertEquals(3, objects.get(3).getNumber());
+
+        assertThrows(IndexOutOfBoundsException.class, () -> objects.add(Integer.MAX_VALUE, XOBJ4));
+    }
+
+    @Test
+    void set()
+    {
+        BaseObjects objects = new BaseObjects();
+
+        assertEquals(0, objects.size());
+
+        assertThrows(IndexOutOfBoundsException.class, () -> objects.set(0, XOBJ1));
+
+        objects.add(XOBJ1);
+        objects.add(XOBJ2);
+        objects.add(XOBJ3);
+
+        objects.set(1, XOBJ4);
+
+        assertSame(XOBJ1, objects.get(0));
+        assertSame(XOBJ4, objects.get(1));
+        assertSame(XOBJ3, objects.get(2));
+    }
+
+    @Test
+    void remove()
+    {
+        BaseObjects objects = new BaseObjects(Arrays.asList(XOBJ1, XOBJ2, XOBJ3));
+
+        assertEquals(3, objects.size());
+
+        objects.remove(0);
+        objects.remove(2);
+
+        assertNull(objects.get(0));
+        assertSame(XOBJ2, objects.get(1));
+        assertNull(objects.get(2));
+
+        assertEquals(3, objects.size());
+    }
+}