java-topology/defects/onlyoffice-0001/test/OnlyOfficeTest.java

package unit;

import java.util.*;

/**
 * OnlyOfficeTest -- CWE-407 benchmark for onlyoffice-0001.
 *
 * onlyoffice-0001: Table.js row/cell membership O(R^2) in table edit operations
 *   sdkjs/word/Editor/Table.js implements table selection, split, merge and
 *   cell operations. Several functions build a small "affected rows" or
 *   "affected cells" array (Rows, RowsIndices, CellsIndexes) from coordinate
 *   hit-testing, then iterate the full table row-by-row calling Array.indexOf()
 *   to test membership in that array:
 *
 *     for (var curRow = 0; curRow < this.Get_RowsCount(); curRow++) {
 *         if (Rows.indexOf(curRow) != -1) { ... }
 *     }
 *
 *   Array.indexOf() is O(A) where A = affected rows/cells length.
 *   The outer loop is O(R) total rows. Combined: O(R * A) per operation.
 *   For a full-row selection or merge, A approaches R, yielding O(R^2).
 *
 *   Affected functions (8 call sites):
 *     SelectCells            -- line 12315: Rows.indexOf(curRow)
 *     VertSplitCells         -- line 12774: RowsIndices.indexOf(curRow)
 *     CalculateNewRowsInfo   -- line 12954: RowsIndices.indexOf(curRow)
 *     HorSplitCells          -- lines 12985, 13158, 13165: CellsIndexes.indexOf(curCell)
 *     GetAffectedCells       -- line 13828: Rows.indexOf(curRow)
 *     CalculateNewRowsInfoByRowsIndices -- line 13895: RowsIndices.indexOf(curRow)
 *
 *   Fix: build a Set from the affected array once before the outer loop.
 *   Set.has() is O(1). Total cost drops from O(R * A) to O(R + A).
 *   At R=500 rows with A=250 affected rows: 125,000 probes -> 500 probes (250x).
 *
 * File:   word/Editor/Table.js
 * Lines:  12315, 12774, 12954, 12985, 13158, 13165, 13828, 13895
 */
public class OnlyOfficeTest {

    // -----------------------------------------------------------------------
    // onlyoffice-0001: Table row membership O(R*A) -> Set.has O(R+A)
    // -----------------------------------------------------------------------

    /**
     * Unpatched: simulate for(curRow=0..R) { if (affectedRows.indexOf(curRow) != -1) }
     * Array.indexOf is O(A) each iteration.
     */
    static long tableSelectUnpatched(int totalRows, int affectedRows) {
        // Build affected rows array (first affectedRows rows are "affected")
        List<Integer> rows = new ArrayList<>(affectedRows);
        for (int i = 0; i < affectedRows; i++) rows.add(i);

        long ops = 0;
        for (int curRow = 0; curRow < totalRows; curRow++) {
            // Array.indexOf -- O(A) worst case
            for (int i = 0; i < rows.size(); i++) {
                ops++;
                if (rows.get(i) == curRow) break;
            }
        }
        return ops;
    }

    /**
     * Patched: build Set once O(A), then Set.has O(1) per row.
     */
    static long tableSelectPatched(int totalRows, int affectedRows) {
        List<Integer> rows = new ArrayList<>(affectedRows);
        for (int i = 0; i < affectedRows; i++) rows.add(i);

        Set<Integer> rowsSet = new HashSet<>(rows);

        long ops = 0;
        for (int curRow = 0; curRow < totalRows; curRow++) {
            ops++; // O(1) hash lookup
            rowsSet.contains(curRow);
        }
        return ops;
    }

    static void testRows(String label, int totalRows, int affectedRows) {
        long unpatched = tableSelectUnpatched(totalRows, affectedRows);
        long patched   = tableSelectPatched(totalRows, affectedRows);
        double ratio   = (double) unpatched / patched;
        System.out.printf("  [%s] R=%d A=%d  unpatched=%d  patched=%d  ratio=%.1fx%n",
                          label, totalRows, affectedRows, unpatched, patched, ratio);
        if (ratio < 2.0) {
            throw new AssertionError(label + ": expected ratio >= 2x, got " + ratio);
        }
    }

    public static void main(String[] args) {
        System.out.println("onlyoffice-0001: Table.js row/cell indexOf O(R*A) -> Set.has O(R+A)");
        System.out.println();

        // Correctness: patched and unpatched produce same set of matched rows
        int R = 100;
        int A = 50;
        List<Integer> affRows = new ArrayList<>();
        for (int i = 0; i < A; i++) affRows.add(i);

        List<Integer> matchedUnpatched = new ArrayList<>();
        List<Integer> matchedPatched   = new ArrayList<>();
        Set<Integer> affSet = new HashSet<>(affRows);

        for (int curRow = 0; curRow < R; curRow++) {
            if (affRows.contains(curRow)) matchedUnpatched.add(curRow);
            if (affSet.contains(curRow))  matchedPatched.add(curRow);
        }

        if (!matchedUnpatched.equals(matchedPatched)) {
            throw new AssertionError("Correctness FAIL: unpatched=" + matchedUnpatched.size()
                + " patched=" + matchedPatched.size());
        }
        System.out.println("  Correctness: both paths match " + matchedPatched.size() + " rows (expected " + A + ")");
        if (matchedPatched.size() != A) {
            throw new AssertionError("Expected " + A + " matched rows, got " + matchedPatched.size());
        }
        System.out.println("  Correctness: PASS");
        System.out.println();

        System.out.println("Performance benchmarks (worst case: A = R/2):");
        testRows("small",   100,    50);
        testRows("medium",  500,   250);
        testRows("large",  1000,   500);
        testRows("xlarge", 5000,  2500);

        System.out.println();
        System.out.println("Performance benchmarks (full selection: A = R):");
        testRows("full-small",  100,  100);
        testRows("full-medium", 500,  500);
        testRows("full-large", 1000, 1000);

        System.out.println();
        System.out.println("PASS");
    }
}