recursive template function leads to negative array size in initialization

https://stackoverflow.com/questions/18539261

26-06-2022
|

Question

I'm working on a matrix class that supports various mathematical operations on matrices. The Matrix class has three template parameters:

template<typename T, int rows, int columns>
class Matrix
{
   ...
};

This is working fine. However, as many operations (such such inverting a matrix and taking its determinant) only work for square matrices (where rows == columns), I chose to make these functions not member functions to control the template parameters and only allow these operations on square matrices:

template<typename T, int rc>
const Matrix<T, rc, rc> inverse (const Matrix<T, rc, rc>& src)
{
    ...
}

I have several functions that operate in this manner.

Now, the error message I'm getting is extremely complicated as the usage of templates has turned what would otherwise be a runtime stack trace into a compile-time stack trace. Here is what I think is happening:

My matrix class stores its data in three ways: a 2d array of pointers, a 1d array of rows, and a 1d array of columns (rows and columns being internal classes declared within matrix the function and function as wrappers for 1d arrays of pointers). All of these pointers point to the Matrix data. This allows for operations over entire rows and columns.
The error I'm getting comes the declaration of these arrays, as well as a few other temporary arrays in the constructor used to initialize the rows and columns. The error message is:

[Error] size of array is negative.
The stack trace is huge, but it goes through the function subMatrix several times. Many of these functions call each other in a roundabout form of recursion.
subMatrix takes a Matrix with m rows and n columns and returns a new matrix with m-1 rows and n-1 columns (one row and one column are removed to create the sub-matrix).
I have made sure that this function is never called on a matrix smaller than 2 x 2 in my code, but I suspect the compiler is not detecting this.
Another function, determinant, calculates the determinant of a square matrix. This function is recursive for matrices larger than 2 x 2. During the recursive part of this function, it calls subMatrix, creating a smaller matrix, until the matrix reaches a size of 2 x 2.
I suspect my problems arise from the compiler seeing recursion in determinant and extrapolating that subMatrix is called on progressively smaller matrices and keeps extrapolating until it reaches a size of -1, which causes an error when declaring the new =, smaller matrix's rows and columns (even though this code would never be executed).

I am completely at a loss as to how to work around this, assuming I have accurate analyzed the situation.

Here is the relevant bits of my code:

//matrix.h
template <typename T, int rows, int columns>

class Matrix
{
public:
    class Column;

    class Row;

private:

    T* m_data[rows][columns];  //errors on these lines.
    Row m_rows[rows];
    Column m_columns[columns];

//    ... much more in class

}

//matrix.cpp

template<typename T, int rows, int columns>
const Matrix<T, rows - 1, columns - 1> Matrix<T, rows, columns>::subMatrix(int row, int column) const
{
    Matrix<T, rows - 1, columns - 1> result;

    if (row > rows || column > columns)
    {
        std::cout << "death: bad bounds\n";
        return result;
    }

    for (int m = 1, mr = 1; m <= rows; m ++)
    {
        if (m == row)
        {
            continue;
        }

        for (int n = 1, nr = 1; n <= columns; n ++)
        {
            if (n == column)
            {
                continue;
            }

            result.at(mr, nr) = *(m_data[m - 1][n - 1]);

            nr ++;
        }

        mr ++;
    }

    return result;
}



template<typename T, int rc>
T minor(const Matrix<T, rc, rc>& src, int m, int n)
{
    return determinant(src.subMatrix(m, n));
}


template<typename T, int rc>
T cofactor(const Matrix<T, rc, rc>& src, int m, int n)
{
    return pow(-1, m + n) * minor(src, m, n);
}



template<typename T, int rc>
T determinant(const Matrix<T, rc, rc>& src)
{
    T det;

    if (rc == 2)
    {
        det = (src.get(1, 1) * src.get(2, 2)) - (src.get(1, 2) * src.get(2, 1));
        return det;
    }

    T temp;

    for (int n = 1; n <= rc; n ++)
    {
        temp = src.get(1, n) * cofactor(src, 1, n);
    }

    return det;
}

It all starts here:

int main(void)
{
    auto m1 = Matrix<int, 3, 3>().map(

     //lambda to fill the matrix with increasing values
     [](int,int,int) { static int n = 0; return ++n; }
    ); 

    int m2 = determinant(m1); //trace leads back to here

    std::cout << m1 << '\n' << m2;

    return 0;
}

And here is the full "stack trace". I doubt it will be that helpful though.

C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>':
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   [ skipping 2 instantiation contexts ]

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.h:21:25: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h:21:25: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h:22:17: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>::Row':
C:\Users\noah dove\Documents\Devcpp\matrix.h:22:17:   required from 'class Matrix<int, -1, -1>'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   [ skipping 3 instantiation contexts ]
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here

C:\Users\noah dove\Documents\Devcpp\matrix.h:105:20: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>':
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   [ skipping 2 instantiation contexts ]
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.h:23:26: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.h: In instantiation of 'class Matrix<int, -1, -1>::Column':
C:\Users\noah dove\Documents\Devcpp\matrix.h:23:26:   required from 'class Matrix<int, -1, -1>'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   [ skipping 3 instantiation contexts ]

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.h:134:17: error: size of array is negative
In file included from C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:1:0:
C:\Users\noah dove\Documents\Devcpp\matrix.cpp: In instantiation of 'Matrix<T, rows, columns>::Matrix(T) [with T = int; int rows = -1; int columns = -1]':
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:365:35:   required from 'const Matrix<T, (rows - 1), (columns - 1)> Matrix<T, rows, columns>::subMatrix(int, int) const [with T = int; int rows = 0; int columns = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'

C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   [ skipping 3 instantiation contexts ]
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:11:25: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:12:28: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.cpp: In instantiation of 'Matrix<T, rows, columns>::Matrix(const Matrix<T, rows, columns>&) [with T = int; int rows = -1; int columns = -1; Matrix<T, rows, columns> = Matrix<int, -1, -1>]':
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:370:10:   required from 'const Matrix<T, (rows - 1), (columns - 1)> Matrix<T, rows, columns>::subMatrix(int, int) const [with T = int; int rows = 0; int columns = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 0]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 1]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   [ skipping 3 instantiation contexts ]
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 2]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:411:40:   required from 'T minor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:419:41:   required from 'T cofactor(const Matrix<T, rc, rc>&, int, int) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:439:3:   required from 'T determinant(const Matrix<T, rc, rc>&) [with T = int; int rc = 3]'
C:\Users\noah dove\Documents\Devcpp\matrix_driver.cpp:9:26:   required from here
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:38:25: error: size of array is negative
C:\Users\noah dove\Documents\Devcpp\matrix.cpp:39:28: error: size of array is negative

If anyone can offer any assistance in this matter, I would be most grateful.

La solution

The special case for rc == 2 shouldn't be a run-time check in the code - it should be a partial specialization, which would terminate the recursion at compile time. Something along these lines:

template <typename T, int rc>
struct DeterminantHelper {
  static T calculate(const Matrix<T, rc, rc>& src) {
    T det;
    for (int n = 1; n <= rc; n ++)
    {
        det = src.get(1, n) * cofactor(src, 1, n);
    }

    return det;
  }
};

template <typename T>
struct DeterminantHelper<T, 2> {
  static T calculate(const Matrix<T, 2, 2>& src) {
    return (src.get(1, 1) * src.get(2, 2)) - (src.get(1, 2) * src.get(2, 1));
  }
};

template<typename T, int rc>
T determinant(const Matrix<T, rc, rc>& src) {
  return DeterminantHelper<T, rc>::calculate(src);
}

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow