[eigen] Segfault in assignment of a product of dense matrix and sparse vector to a sparse vector.

["Sergey Morozov" <sergey.morozov@xxxxxxxxxxxxxx>]

Hi all,

First of all, I'd like to thank all Eigen developers for such a great
library. We are using Eigen3 extensively in our optimization library.

Recently we by acсident assigned a product of dense matrix and sparse vector
to a sparse vector. This operation leads to the segfault at runtime. The
simplest way to reproduce:

    #include <iostream>
    #include <Eigen/Dense>
    #include <Eigen/Sparse>
    using namespace Eigen;

    #define N  4

    int main(){
      typedef SparseMatrix<double,RowMajor> SparseMatrixD;
      typedef SparseVector<double> SparseVectorD;
    
      MatrixXd A( MatrixXd::Random( N, N ) );
    
      SparseVectorD y(N);
      y.insert(0) = 1.;
      y.insert(2) = 1.;
      y.finalize();

      SparseVectorD N);
      /* SEGFAULT in: */
      x = A * y;
      return 0;
    };

Analysis of the problem reveals the following.

1. Result of "A*y" product is DenseTimeSparseProduct <- ProductBase <-
MatrixBase.

2. Now we assign result of "A*y" to x. SparseVector has only the following
assignment operators:

    inline SparseVector& operator=(const SparseVector& other)

    template<typename OtherDerived>
    inline SparseVector& operator=(const SparseMatrixBase<OtherDerived>&
other)

    template<typename Lhs, typename Rhs>

    inline SparseVector& operator=(const SparseSparseProduct<Lhs,Rhs>&
product)

3. So compiler implicitly converts DenseTimeSparseProduct to SparseVector
using

    template<typename OtherDerived>
    inline SparseVector(const MatrixBase<OtherDerived>& other)
      : m_size(0)
    {
      *this = other.derived();
    }

4. The problem is that other.derived() is again DenseTimeSparseProduct and
the assignment to *this again doesn't exist. So we have an infinite loop!
Let's check this in gdb (backtrace):

    (gdb) fr 10000
    #10000 0x08048ff1 in
SparseVector<Eigen:enseTimeSparseProduct<Eigen::Matrix<double,
-0x00000000000000001, -0x00000000000000001, 0, -0x00000000000000001,
-0x00000000000000001>, Eigen::SparseVector<double, 0, int> > >
(this=0xbf69c428,
        other=...) at
/home/user/opt/eigen-3.0.0/include/Eigen/src/Sparse/SparseVector.h:203
    203              *this = other.derived();

So, one should decide if the assignment of dense matrix and sparse vector to
sparse vector is legal or not. In both cases the fix is simple - just
implement

    template<typename OtherDerived>
    inline SparseVector& operator=(const MatrixBase<OtherDerived>& other)

method. In the later case just add "Not supported" assert. We are ready to
provide the patch for both solutions.

Best regards,
Sergey Morozov