SparseCore: Fix random insertion when StorageIndex is wider than Index

libeigen/eigen!3379

Co-authored-by: Rasmus Munk Larsen <rmlarsen@gmail.com>

Eigen/src/SparseCore/SparseMatrix.h

diff --git a/Eigen/src/SparseCore/SparseMatrix.h b/Eigen/src/SparseCore/SparseMatrix.h
index 1a9ac8d..4a90737 100644
--- a/Eigen/src/SparseCore/SparseMatrix.h
+++ b/Eigen/src/SparseCore/SparseMatrix.h
@@ -1725,7 +1725,11 @@
     std::iota(m_outerIndex, m_outerIndex + m_outerSize + 1, StorageIndex(0));
   } else {
     // check for integer overflow: if maxReserveSize == 0, insertion is not possible
-    Index maxReserveSize = static_cast<Index>(NumTraits<StorageIndex>::highest()) - m_data.allocatedSize();
+    // StorageIndex can be wider than Index (long long with a 32-bit Index), so clamp its maximum to Index's.
+    using WideIndex = typename std::common_type<Index, StorageIndex>::type;
+    const Index maxSize =
+        static_cast<Index>(numext::mini<WideIndex>(NumTraits<StorageIndex>::highest(), NumTraits<Index>::highest()));
+    Index maxReserveSize = maxSize - m_data.allocatedSize();
     eigen_assert(maxReserveSize > 0);
     if (m_outerSize <= maxReserveSize) {
       // allocate space for one additional element per vector

test/CMakeLists.txt

diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
index f17cdef..34a088a 100644
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -502,6 +502,7 @@
 ei_add_test(sparse_scatter)
 ei_add_test(sparse_block)
 ei_add_test(sparse_vector)
+ei_add_test(sparse_int_index)
 ei_add_test(sparse_product)
 ei_add_test(sparse_threaded_product "-pthread" "${CMAKE_THREAD_LIBS_INIT}")
 ei_add_test(sparse_ref)

test/sparse_int_index.cpp

diff --git a/test/sparse_int_index.cpp b/test/sparse_int_index.cpp
new file mode 100644
index 0000000..4f670b4
--- /dev/null
+++ b/test/sparse_int_index.cpp
@@ -0,0 +1,58 @@
+// SPDX-FileCopyrightText: The Eigen Authors
+// SPDX-License-Identifier: MPL-2.0
+
+// Index is int here, as on 32-bit targets, so that a StorageIndex can be wider than Index.
+#ifdef EIGEN_DEFAULT_DENSE_INDEX_TYPE
+#undef EIGEN_DEFAULT_DENSE_INDEX_TYPE
+#endif
+#define EIGEN_DEFAULT_DENSE_INDEX_TYPE int
+#include "main.h"
+
+#include <Eigen/SparseCore>
+
+// Random insertion past the reserved room must grow the storage. Its growth limit is NumTraits<StorageIndex>::highest()
+// clamped to Index; a StorageIndex wider than Index used to wrap the limit to -1, so the insertion wrote past the end
+// of the storage instead.
+template <typename StorageIndex, int Options>
+void sparse_random_insertion_growth(bool reserveFirst) {
+  using SpMat = SparseMatrix<double, Options, StorageIndex>;
+  using DenseMat = Matrix<double, Dynamic, Dynamic>;
+  const Index rows = internal::random<Index>(2, 40);
+  const Index cols = internal::random<Index>(2, 40);
+
+  // Every coefficient, in random order, so that most insertions find no free slot in their inner vector.
+  std::vector<Index> order(rows * cols);
+  for (Index k = 0; k < rows * cols; ++k) order[k] = k;
+  for (Index k = rows * cols - 1; k > 0; --k) std::swap(order[k], order[internal::random<Index>(0, k)]);
+
+  SpMat A(rows, cols);
+  if (reserveFirst) A.reserve(VectorXi::Constant(A.outerSize(), 1));
+  DenseMat ref = DenseMat::Zero(rows, cols);
+  for (Index k : order) {
+    const Index i = k % rows, j = k / rows;
+    A.insert(i, j) = ref(i, j) = double(k + 1);
+  }
+  VERIFY_IS_EQUAL(A.nonZeros(), rows * cols);
+  VERIFY_IS_EQUAL(A.innerIndicesAreSorted(), A.outerSize());
+  VERIFY_IS_EQUAL(DenseMat(A), ref);
+
+  A.makeCompressed();
+  VERIFY(A.isCompressed());
+  VERIFY_IS_EQUAL(DenseMat(A), ref);
+}
+
+template <typename StorageIndex>
+void sparse_random_insertion_growth() {
+  for (bool reserveFirst : {false, true}) {
+    sparse_random_insertion_growth<StorageIndex, ColMajor>(reserveFirst);
+    sparse_random_insertion_growth<StorageIndex, RowMajor>(reserveFirst);
+  }
+}
+
+EIGEN_DECLARE_TEST(sparse_int_index) {
+  STATIC_CHECK(sizeof(Index) == sizeof(int));
+  for (int i = 0; i < g_repeat; ++i) {
+    CALL_SUBTEST_1(sparse_random_insertion_growth<long long>());
+    CALL_SUBTEST_2(sparse_random_insertion_growth<int>());
+  }
+}