bug 59212: Do not check for overlapping regions when adding merged regions to a sheet

git-svn-id: https://svn.apache.org/repos/asf/poi/trunk@1736155 13f79535-47bb-0310-9956-ffa450edef68

5 files changed, 139 insertions, 59 deletions

diff --git a/src/java/org/apache/poi/hssf/usermodel/HSSFSheet.java b/src/java/org/apache/poi/hssf/usermodel/HSSFSheet.java
index e4b0068333..a8cf33176d 100644
--- a/src/java/org/apache/poi/hssf/usermodel/HSSFSheet.java
+++ b/src/java/org/apache/poi/hssf/usermodel/HSSFSheet.java
@@ -660,28 +660,75 @@ public final class HSSFSheet implements org.apache.poi.ss.usermodel.Sheet {
     }
 
     /**
+     * Adds a merged region of cells on a sheet.
+     *
+     * @param region to merge
+     * @return index of this region
+     * @throws IllegalArgumentException if region contains fewer than 2 cells
+     * @throws IllegalStateException if region intersects with a multi-cell array formula
+     * @throws IllegalStateException if region intersects with an existing region on this sheet
+     */
+    @Override
+    public int addMergedRegion(CellRangeAddress region) {
+        return addMergedRegion(region, true);
+    }
+
+    /**
+     * Adds a merged region of cells (hence those cells form one).
+     * Skips validation. It is possible to create overlapping merged regions
+     * or create a merged region that intersects a multi-cell array formula
+     * with this formula, which may result in a corrupt workbook.
+     *
+     * To check for merged regions overlapping array formulas or other merged regions
+     * after addMergedRegionUnsafe has been called, call {@link #validateMergedRegions()}, which runs in O(n^2) time.
+     *
+     * @param region to merge
+     * @return index of this region
+     * @throws IllegalArgumentException if region contains fewer than 2 cells
+     */
+    @Override
+    public int addMergedRegionUnsafe(CellRangeAddress region) {
+        return addMergedRegion(region, false);
+    }
+
+    /**
+     * Verify that merged regions do not intersect multi-cell array formulas and
+     * no merged regions intersect another merged region in this sheet.
+     *
+     * @throws IllegalStateException if region intersects with a multi-cell array formula
+     * @throws IllegalStateException if at least one region intersects with another merged region in this sheet
+     */
+    @Override
+    public void validateMergedRegions() {
+        checkForMergedRegionsIntersectingArrayFormulas();
+        checkForIntersectingMergedRegions();
+    }
+
+    /**
      * adds a merged region of cells (hence those cells form one)
      *
      * @param region (rowfrom/colfrom-rowto/colto) to merge
+     * @param validate whether to validate merged region
      * @return index of this region
      * @throws IllegalArgumentException if region contains fewer than 2 cells
      * @throws IllegalStateException if region intersects with an existing merged region
      * or multi-cell array formula on this sheet
      */
-    @Override
-    public int addMergedRegion(CellRangeAddress region) {
+    private int addMergedRegion(CellRangeAddress region, boolean validate) {
         if (region.getNumberOfCells() < 2) {
             throw new IllegalArgumentException("Merged region " + region.formatAsString() + " must contain 2 or more cells");
         }
         region.validate(SpreadsheetVersion.EXCEL97);
 
-        // throw IllegalStateException if the argument CellRangeAddress intersects with
-        // a multi-cell array formula defined in this sheet
-        validateArrayFormulas(region);
+        if (validate) {
+            // throw IllegalStateException if the argument CellRangeAddress intersects with
+            // a multi-cell array formula defined in this sheet
+            validateArrayFormulas(region);
         
-        // Throw IllegalStateException if the argument CellRangeAddress intersects with
-        // a merged region already in this sheet
-        validateMergedRegions(region);
+            // Throw IllegalStateException if the argument CellRangeAddress intersects with
+            // a merged region already in this sheet
+            validateMergedRegions(region);
+        }
 
         return _sheet.addMergedRegion(region.getFirstRow(),
                 region.getFirstColumn(),
@@ -716,7 +763,19 @@ public final class HSSFSheet implements org.apache.poi.ss.usermodel.Sheet {
         }
 
     }
-    
+
+    /**
+     * Verify that none of the merged regions intersect a multi-cell array formula in this sheet
+     *
+     * @param region
+     * @throws IllegalStateException if candidate region intersects an existing array formula in this sheet
+     */
+    private void checkForMergedRegionsIntersectingArrayFormulas() {
+        for (CellRangeAddress region : getMergedRegions()) {
+            validateArrayFormulas(region);
+        }
+    }
+
     private void validateMergedRegions(CellRangeAddress candidateRegion) {
         for (final CellRangeAddress existingRegion : getMergedRegions()) {
             if (existingRegion.intersects(candidateRegion)) {
@@ -727,6 +786,27 @@ public final class HSSFSheet implements org.apache.poi.ss.usermodel.Sheet {
     }
 
     /**
+     * Verify that no merged regions intersect another merged region in this sheet.
+     *
+     * @throws IllegalStateException if at least one region intersects with another merged region in this sheet
+     */
+    private void checkForIntersectingMergedRegions() {
+        final List<CellRangeAddress> regions = getMergedRegions();
+        final int size = regions.size();
+        for (int i=0; i < size; i++) {
+            final CellRangeAddress region = regions.get(i);
+            for (final CellRangeAddress other : regions.subList(i+1, regions.size())) {
+                if (region.intersects(other)) {
+                    String msg = "The range " + region.formatAsString() +
+                                " intersects with another merged region " +
+                                other.formatAsString() + " in this sheet";
+                    throw new IllegalStateException(msg);
+                }
+            }
+        }
+    }
+
+    /**
      * Control if Excel should be asked to recalculate all formulas on this sheet
      * when the workbook is opened.
      * <p/>
diff --git a/src/java/org/apache/poi/ss/usermodel/Sheet.java b/src/java/org/apache/poi/ss/usermodel/Sheet.java
index 38986bbdde..cba701d9e6 100644
--- a/src/java/org/apache/poi/ss/usermodel/Sheet.java
+++ b/src/java/org/apache/poi/ss/usermodel/Sheet.java
@@ -277,6 +277,30 @@ public interface Sheet extends Iterable<Row> {
     int addMergedRegion(CellRangeAddress region);
 
     /**
+     * Adds a merged region of cells (hence those cells form one).
+     * Skips validation. It is possible to create overlapping merged regions
+     * or create a merged region that intersects a multi-cell array formula
+     * with this formula, which may result in a corrupt workbook.
+     *
+     * To check for merged regions overlapping array formulas or other merged regions
+     * after addMergedRegionUnsafe has been called, call {@link #validateMergedRegions()}, which runs in O(n^2) time.
+     *
+     * @param region to merge
+     * @return index of this region
+     * @throws IllegalArgumentException if region contains fewer than 2 cells
+     */
+    int addMergedRegionUnsafe(CellRangeAddress region);
+
+    /**
+     * Verify that merged regions do not intersect multi-cell array formulas and
+     * no merged regions intersect another merged region in this sheet.
+     *
+     * @throws IllegalStateException if region intersects with a multi-cell array formula
+     * @throws IllegalStateException if at least one region intersects with another merged region in this sheet
+     */
+    void validateMergedRegions();
+
+    /**
      * Determines whether the output is vertically centered on the page.
      *
      * @param value true to vertically center, false otherwise.
diff --git a/src/ooxml/java/org/apache/poi/xssf/streaming/SXSSFSheet.java b/src/ooxml/java/org/apache/poi/xssf/streaming/SXSSFSheet.java
index 4f1c47ccad..ce1a8cf8bf 100644
--- a/src/ooxml/java/org/apache/poi/xssf/streaming/SXSSFSheet.java
+++ b/src/ooxml/java/org/apache/poi/xssf/streaming/SXSSFSheet.java
@@ -389,6 +389,30 @@ public class SXSSFSheet implements Sheet, Cloneable
     }
 
     /**
+     * Adds a merged region of cells (hence those cells form one)
+     *
+     * @param region (rowfrom/colfrom-rowto/colto) to merge
+     * @return index of this region
+     */
+    @Override
+    public int addMergedRegionUnsafe(CellRangeAddress region)
+    {
+        return _sh.addMergedRegionUnsafe(region);
+    }
+
+    /**
+     * Verify that merged regions do not intersect multi-cell array formulas and
+     * no merged regions intersect another merged region in this sheet.
+     *
+     * @throws IllegalStateException if region intersects with a multi-cell array formula
+     * @throws IllegalStateException if at least one region intersects with another merged region in this sheet
+     */
+    @Override
+    public void validateMergedRegions() {
+        _sh.validateMergedRegions();
+    }
+
+    /**
      * Determines whether the output is vertically centered on the page.
      *
      * @param value true to vertically center, false otherwise.
diff --git a/src/ooxml/java/org/apache/poi/xssf/usermodel/XSSFSheet.java b/src/ooxml/java/org/apache/poi/xssf/usermodel/XSSFSheet.java
index b62d1a5e96..f5b531414c 100644
--- a/src/ooxml/java/org/apache/poi/xssf/usermodel/XSSFSheet.java
+++ b/src/ooxml/java/org/apache/poi/xssf/usermodel/XSSFSheet.java
@@ -323,6 +323,7 @@ public class XSSFSheet extends POIXMLDocumentPart implements Sheet {
      * @return index of this region
      * @throws IllegalArgumentException if region contains fewer than 2 cells
      */
+    @Override
     public int addMergedRegionUnsafe(CellRangeAddress region) {
         return addMergedRegion(region, false);
     }
@@ -408,7 +409,6 @@ public class XSSFSheet extends POIXMLDocumentPart implements Sheet {
         }
     }
 
-
     /**
      * Verify that candidate region does not intersect with an existing merged region in this sheet
      *
@@ -452,6 +452,7 @@ public class XSSFSheet extends POIXMLDocumentPart implements Sheet {
      * @throws IllegalStateException if region intersects with a multi-cell array formula
      * @throws IllegalStateException if at least one region intersects with another merged region in this sheet
      */
+    @Override
     public void validateMergedRegions() {
         checkForMergedRegionsIntersectingArrayFormulas();
         checkForIntersectingMergedRegions();
diff --git a/src/ooxml/testcases/org/apache/poi/xssf/usermodel/TestXSSFSheet.java b/src/ooxml/testcases/org/apache/poi/xssf/usermodel/TestXSSFSheet.java
index f5ad27c815..2b7616a29c 100644
--- a/src/ooxml/testcases/org/apache/poi/xssf/usermodel/TestXSSFSheet.java
+++ b/src/ooxml/testcases/org/apache/poi/xssf/usermodel/TestXSSFSheet.java
@@ -27,7 +27,6 @@ import static org.junit.Assert.assertNull;
 import static org.junit.Assert.assertSame;
 import static org.junit.Assert.assertTrue;
 import static org.junit.Assert.fail;
-import static org.junit.Assume.assumeTrue;
 
 import java.io.IOException;
 import java.util.Arrays;
@@ -303,54 +302,6 @@ public final class TestXSSFSheet extends BaseTestSheet {
         workbook.close();
     }
 
-    /**
-     * bug 58885: checking for overlapping merged regions when
-     * adding a merged region is safe, but runs in O(n).
-     * the check for merged regions when adding a merged region
-     * can be skipped (unsafe) and run in O(1).
-     */
-    @Test
-    public void addMergedRegionUnsafe() throws IOException {
-        XSSFWorkbook wb = new XSSFWorkbook();
-        XSSFSheet sh = wb.createSheet();
-        CellRangeAddress region1 = CellRangeAddress.valueOf("A1:B2");
-        CellRangeAddress region2 = CellRangeAddress.valueOf("B2:C3");
-        CellRangeAddress region3 = CellRangeAddress.valueOf("C3:D4");
-        CellRangeAddress region4 = CellRangeAddress.valueOf("J10:K11");
-        assumeTrue(region1.intersects(region2));
-        assumeTrue(region2.intersects(region3));
-
-        sh.addMergedRegionUnsafe(region1);
-        assertTrue(sh.getMergedRegions().contains(region1));        
-
-        // adding a duplicate or overlapping merged region should not
-        // raise an exception with the unsafe version of addMergedRegion.
-           
-        sh.addMergedRegionUnsafe(region2);
-
-        // the safe version of addMergedRegion should throw when trying to add a merged region that overlaps an existing region
-        assertTrue(sh.getMergedRegions().contains(region2));
-        try {
-            sh.addMergedRegion(region3);
-            fail("Expected IllegalStateException. region3 overlaps already added merged region2.");
-        } catch (final IllegalStateException e) {
-            // expected
-            assertFalse(sh.getMergedRegions().contains(region3));
-        }
-        // addMergedRegion should not re-validate previously-added merged regions
-        sh.addMergedRegion(region4);
-
-        // validation methods should detect a problem with previously added merged regions (runs in O(n^2) time)
-        try {
-            sh.validateMergedRegions();
-            fail("Expected validation to fail. Sheet contains merged regions A1:B2 and B2:C3, which overlap at B2.");
-        } catch (final IllegalStateException e) {
-            // expected
-        }
-
-        wb.close();
-    }
-
     @Test
     public void setDefaultColumnStyle() throws IOException {
         XSSFWorkbook workbook = new XSSFWorkbook();