Compiler Generated Identity Matrices

[3hM2Nwbp]

The title says it all. Unfortunately, I am too dumb to wrap my head around this given all of the restrictions imposed on constexpr constructs (no defining variables, etc).

Identity matrices are in the following pattern:

3x3 Array
{1, 0, 0},
{0, 1, 0},
{0, 0, 1}

4x4 Array
{1, 0, 0, 0},
{0, 1, 0, 0},
{0, 0, 1, 0},
{0, 0, 0, 1}

Given the following:

template<typename T, uint32_t X, uint32_t Y>
class Matrix;

template<typename T, uint32_t X, uint32_t Y>
constexpr Matrix<T, X, Y> genIdentityMatrix()
{
  // <insert magic here, above, and below>
}

template<typename T, uint32_t X, uint32_t Y>
class Matrix
{
  static constexpr Matrix<T, X, Y> IDENTITY = genIdentityMatrix<T, X, Y>();
};

I'm 99.9% sure this is possible, but meta-programming really scares the hell out of me. Can anyone point me in the right direction?

* Just make believe that there isn't a problem with the order of declarations / visibility in the above code. My head hurts too much right now.

[J4ke]

Well, if you have an array and you know the size, you can just iterate over the array and set the first value in the first row to 1 and the rest to 0, the second element in the second row (sense a pattern?). Since you know what row you are iterating over (just the variable you're using for your outer for-loop), you can figure out where to place the one.

[3hM2Nwbp]

Sorry, but I think that you've misinterpreted my situation. Looping cannot be used in constexpr methods, as they define variables.

The use of constexpr on a function imposes some limitations on what that function can do. First, the function must have a non-void return type. Second, the function body cannot declare variables or define new types. Third, the body may only contain declarations, null statements and a single return statement. There must exist argument values such that, after argument substitution, the expression in the return statement produces a constant expression.

The effect of using constant expressions is that the value is generated at compile-time, rather than run-time.

[naraku9333]

Does it have to be constexpr?
http://ideone.com/bvkIx8

[3hM2Nwbp]

Well, right now I have it evaluated at run-time (static member of template). I've typed up a bit below...there are a few utility classes that are used as well, so it's only a summary.

	// Quick type up, might contain errors.
	template<typename T, uint32_t X, uint32_t Y>
	class Matrix
	{
		MultiArray<T, X, Y> values;
		constexpr static uint32_t ROW_COUNT = X;
		constexpr static uint32_t COLUMN_COUNT = Y;

		
	  public:

		constexpr static MultiArray<T, X, Y> genZero()
		{
			return MultiArray<T, X, Y> {};
		}
		
		// Generated By Compiler (great!)
		constexpr static Matrix<T, X, Y> ZERO = Matrix<T, X, Y>(genZero());

		static Matrix<T, X, Y> genIdentity()
		{
			MultiArray<T, X, Y> rv;
			for(int i = 0; i < X && i < Y; ++i)
			{
				rv[i][i] = static_cast<T>(1);
			}
			return rv;
		}

		// Generated at runtime
		const static Matrix<T, X, Y> IDENTITY = genIdentity();

I just figured that if it could be generated beforehand, why not? (other than the fact I can't figure out how to!) It'd be a clever solution at any rate.

I'm more interested in the solution itself than any micro-optimizations it might provide at this point.

[JLBorges]

Something like this, perhaps?

#include <iostream>

template < typename T, std::size_t ROWS, std::size_t COLS = ROWS >
struct identity_matrix
{
    struct row
    {
        constexpr explicit row( std::size_t r ) : i(r) {}

        constexpr T operator[] ( std::size_t j ) const
        { return i<ROWS && j<COLS ? j==i : ( throw "out of range", -1 ) ; }

        const std::size_t i ;
    };

    constexpr row operator[] ( std::size_t i ) const { return row(i) ; }
};

template < typename T, std::size_t ROWS, std::size_t COLS = ROWS >
struct matrix
{
    static constexpr identity_matrix<T,ROWS,COLS> identity {} ;
};

int main()
{
    constexpr auto m = matrix<int,100>::identity ;

    for( int test = 0 ; test < 4 ; ++test )
    {
        switch(test)
        {
            case m[5][5] * m[5][6] :
            {
                const char cstr[ ( m[3][3] + m[5][5] ) * 5 ] = "test == 0" ;
                std::cout << cstr << '\n' ;
            }
            break ;

            case m[2][2] : std::cout << "test == 1\n" ; break ;

            case m[2][2] + m[3][3] : std::cout << "test == 2\n" ; break ;

            default : std::cout << "default\n" ;
        }
    }
}

http://coliru.stacked-crooked.com/a/ed15cc5dae7cf1b0

[3hM2Nwbp]

You sir, just blew my mind. I NEVER thought about using ternary operators!

Thanks!

_{Now if you'll excuse me, I'll be running away to play with this like a kid that just got a new toy.}

[Cubbi]

You can't quite build your static constexpr member from the type returned by getIdentityMatrix because the type is incomplete within its own definition (under C++11 -- I think it was fixed in C++14 exactly because of this, very common, stumbling block)

As to how to build the matrix - yes, constexpr programming under C++11 is all about ternary operators (as you can see for example at http://en.cppreference.com/w/cpp/language/constexpr ), but for variety, consider index_sequence - based solution

#include <iostream>
#include <array>
#include <cstdint>

// crude C++14'ish integer_sequence. 
// Better one is at http://stackoverflow.com/a/17426611/273767
// Even better one will be in your #include <utility> some day
template<int ...> struct seq { };
template<int N, int ...S> struct gens : gens<N-1, N-1, S...> { };
template<int ...S> struct gens<0, S...> { typedef seq<S...> type; };

// given position in the 1D representation of an X*Y matrix,
// return the value to put in that cell
template<std::uint32_t X, std::uint32_t Y>
constexpr int get_element(int pos)
{
    return pos % Y == pos / Y; // 1 if row == col, 0 otherwise
}

// build the 1D representation of the matrix
template <typename T, std::uint32_t X, std::uint32_t Y, int ...S>
constexpr std::array<T, X*Y> get_identity_array(seq<S...>) {
    return std::array<T, X*Y>{{get_element<X,Y>(S)...}};
}

// little constexpr tag type to select the right constructor
struct identity_t { constexpr identity_t() {} };
constexpr identity_t identity_tag;

template<typename T, std::uint32_t X, std::uint32_t Y>
class Matrix
{
    std::array<T, X*Y> data; // I'm a fan of linear backing storage
 public:
    // default ctor, zeroes out the matrix
    constexpr Matrix() : data() {}

    // identity matrix constructor
    constexpr Matrix(identity_t) : data(get_identity_array<T,X,Y>( typename gens<X*Y>::type() )) {}

    T& operator()(std::uint32_t row, std::uint32_t col) { return data[row*Y + col]; }
    constexpr T operator()(std::uint32_t row, std::uint32_t col) const { return data[row*Y + col]; }
};

int main()
{
     constexpr Matrix<int, 5, 5> m(identity_tag);

     std::array<int, m(0,0)> a; // test constexpr-ness

     for(int row = 0; row < 5; ++row)
     {
         for(int col = 0; col < 5; ++col)
             std::cout << m(row, col) << ' ';
         std::cout << '\n';
     }
}

live: http://coliru.stacked-crooked.com/a/6447c2f873b70fdb

[JLBorges]

> given all of the restrictions imposed on constexpr constructs (no defining variables, etc).

This should interest you: http://isocpp.org/files/papers/N3652.html

[3hM2Nwbp]

Every time I think I'm on top of the language, I get a curve-ball like this. I'll have to study your code a bit more...metaprogramming is not quite what I'm used to.

Absolutely brilliant, thanks again.

[3hM2Nwbp]

You can't quite build your static constexpr member from the type returned by getIdentityMatrix because the type is incomplete within its own definition

Well then...is this legal? Seems to compile with GCC and clang. Is it doing what I want? I have no idea how to even check to be honest.

http://ideone.com/ST5tF1

[Cubbi]

functions are fine (besides, your IDENTITY() isn't constexpr anyway, you need something like

static constexpr Matrix IDENTITY() {
    return Matrix{get_identity_array<T,X,Y>( typename gens<X*Y>::type() )};
}

(and make the read-only accessor a const member function after that)

but if you were going with the idea from the original post and wrote

static const constexpr Matrix IDENTITY {get_identity_array<T,X,Y>( typename gens<X*Y>::type() )};

you'd get an okay from g++-4.8.1, but a fail from

clang:

test.cc:36:31: error: constexpr variable cannot have non-literal type 'const rebel::Matrix<float, 4, 4>'
static const constexpr Matrix IDENTITY {get_identity_array<T,X,Y>( typename gens<X*Y>::type() )};
                              ^

and intel:

test.cc(36): error: a constexpr static data member cannot be declared with an incomplete type "const rebel::Matrix<T, X, Y>"
              static const constexpr Matrix IDENTITY {get_identity_array<T,X,Y>( typename gens<X*Y>::type() )};
                                            ^

(intel's diagnostic here is more user-friendly)

[3hM2Nwbp]

I did encounter that error from clang, and it had me checking the type with std::is_literal_type before I figured out it was a bogus message. I was quite surprised, clang is usually spot-on...

I think what I'm going to do is include both, commenting out the C++14 version for now.

Thanks!