Wednesday, September 26, 2007

Working around cv-qualifiers when specializing template classes

A great principle states that "libraries should be open to extension and closed to modification". This article tries to address an inconvenience when writing generic libraries that are extensible by the means of template specialization.

Imagine a generic class that implements a hashed set. It's signature would be something like:


template <class Key, class Hash = hash<Key>>
class hash_set;


Unless the user doesn't specify a hashing function explicitly the library uses a specialization of its 'hash' class. One such class would look something like:


template <class T>
struct hash
{
  size_t operator () (const T& x) const {
    return ???;
  }
};


Suddenly a problem occurs - we don't know how to hash every possible type. We'll just have to go with specializations and leave the unspecialized class undefined so that a compile-time error is raised if the hash doesn't know how to do so.


template <class T> struct hash;


Now, a concise library writer would provide specializations for the hash class for some basic types, so that the hash_set is immediately useful for simple cases.


template <> struct hash<char> {...}
template <> struct hash<short> {...}
template <> struct hash<int> {...}
template <> struct hash<char*> {...}
template <> struct hash<std::string> {...}
template <> struct hash<etc.> {...}


Now, our user can specialize the hash class for custom types and thus extend the library's reach.

As our users happily trek along different instantiations of the hash_set template suddenly a calamity strikes! Our user tries to instantiate a hash_set<const int>. Of course the compiler complains that no such specialization of hash<> exists. The user is discontent, the library vendor is in a stupor. A common scenario, really.

The tedious solution in such cases is to write a specialization for both const and non-const types. Yuck.

Luckily for us Boost provides a nice feature in its TypeTraits library - remove_const. Using it we can rewrite our hash_set as follows:


template <class Key, class Hash = hash<typename boost::remove_const<Key>::type>>
class hash_set;


Excellent. However, if our library vendor ever wants to write another class that uses a hash, for example a hash_map, they have to remember to add the remove_const bit. Each time. And what if our const remover happens to change?

Being smart about code responsibilities we come up with the following solution - the const remover will become a part of the hashing library, instead of the container library:


template <class T>
struct select_hash {
  typedef hash<typename boost::remove_const<T>::type> type;
};


or even better:


template <class T>
struct select_hash
  : hash<typename boost::remove_const<T>::type>
{};


Thus usage becomes:
template <class Key, class Hash = select_hash<Key>>
class hash_set;

Now we're set for clear sailing. Yet there is a way to be even cleverer, thus removing the need of select_hash and relying solely on hash. Observe as we change our unspecialized template:


template <class T>
struct hash
  : hash<typename boost::remove_const<T>::type>
{};


Now each instantiation of hash<> either stumbles on a perfect specialization (like hash<int>), or the generic one, that first tries to strip the const qualifier. Thus, a hash<const int> inherits hash<int> and it's a perfect circle. When used with a type that hash has no specialization for, the compiler raises an error that 'a class cannot inherit from itself'. We're done here.

Note: to remove the volatile qualifier as well use boost::remove_cv<>. Depending on your situation this may or may not be a useful move.

Tuesday, September 18, 2007

The Missing Things in C++

These are a few of the things that we mused would be (if not practical, then at least) interesting to have.

dont - keyword, doesn't do what's in its block:

dont {
   cout << "this program is stupid" << endl; //yep, it's not
   remove("win.com"); //definitely don't do this
   crash(); //d'oh
}


Possible implementation with standard C++:

#define dont if(false)


that - keyword, similar to this, a pointer to a random instance of a class:

void someclass::somemethod()
{
   that->m_var = 10; //someone got a ten, good luck...
}


Unfortunately a clean implementation in the current standard is impossible, but can be done intrusively like so:

template <class T>
class _thatable
{
protected:
   _thatable() { m_thats.push_back(this); }
   ~_thatable() { m_thats.erase(find(m_thats.begin(), m_thats.end(), this)); }
   T* _my_that() {
      return m_thats[rand()%m_thats.size()];
   }
private:
   static vector<T*> m_thats;
};

#define cool_class(x) class x : public _thatable<x>
#define that _my_that()

... and used like so:

cool_class(myclass) , public other_parent
{
...
};


#outclude - preprocessor, removes all declarations that were previously brought in with an #include

#outclude <vector>
...
vector<int> a; // ERROR


Unfortunately, it's impossible to implement with the current standard.

maybe - keyword, sometimes returns true, sometimes false...


   bool hmm = maybe;
   if( hmm )
      cout << "Hello, world" ;
   else
      dont { cout << "Hello, world"; }

Pretty straightforward to implement:

struct {
   operator bool () const {
      return rand() % 2;
   }
} maybe;


disusing and disusing namespace - removes a symbol or all symbols in a namespace from the current scope.

disusing namespace std;
string str; // huh?..


private_cast and protected_cast - similar to const_cast, allows access to otherwise inaccessible sections of a class.


class { int b; } a;
private_cast(a).b = 5;


private_cast is impossible to implement in general. protected_cast on the other hand can be implemented in several ways.

Monday, September 17, 2007

Office Pranks

Here is a list of office pranks, that we have made.

1. Jam the chair under the desk.
Office chairs have adjustable height. If you roll the chair under the desk, you can adjust its height so it gets jammed under the desk and it's pretty hard to get it out of there. The cool thing is you cannot know if this prank is done, unless you actually try to pull the chair out of the desk, leaving you with a stupid look on your face.
Times done: A lot!
Priceless reactions: "Good morning! Now let me... hm... NOT AGAIN" (unfortunately you have to *see* the person's reaction to really appreciate it)
Rating: 5/10

2. Duct tape on the bottom of the mouse
I bet this prank has been done to the owner of the first mouse ever. It's pretty old.
Times done: 5-6 (there was a time when everybody looked the bottom of their mouses for duct tape, so it got old quickly)
Priceless reactions: "That's odd" *circles with the mouse* "I think my mouse is broken..." "Hey I need a new mouse!"
Rating: 4/10

3. Clippy
If you don't want to read the Clippy site, it's the paperclip from MS Office made as a desktop application, which gives you random ridiculous (but not obviously ridiculous) suggestions to help you.
Times done: 5-6
Priceless reactions: "Microsoft cannot have made something THAT idiotic with the new update!" "What the... I KNOW I can use my mouse to click on things!" "Have you seen this new feature with Windows Vista? The paperclip with the suggestions to help you! Vista sucks!"
Rating: 8/10 if they bite (Just watching their facial expressions the first 3-4 times that Clippy shows is worth it! Never mind what they say)

4. The art director and the word 'ass'
I don't even know how that started. It consists of somehow placing the written word "ass" in the view of our art director. It really pissed him off, so naturally, it was fun. So far we've managed to put it: on a sticky note on his PC; as his desktop wallpaper; as an icon for an internal tool of ours; as a 3D model suggestion; as a logo suggestion for the game; as a job application; in a "readme.txt" file on his desktop. This prank died lately but this blog reminded me that it could be restarted.
Times done: Too many
Priceless reactions: "He he. That's funny" "Ha. Ha. Ha." "Alright. Ass. I see." "Well it's good, but it's enough now." "Stop it guys. Seriously." "I mean, really, stop it!" "Aaaaah! *goes crazy*" ... ... "What?! No 'ass' today?"
Rating: 7/10

5. Spin and hit

That's not us, though. That's where we got the idea.
Times done: once
Priceless reactions: see video.
Rating: 9/10

6. The secret handshake
I don't remember where that came from either. Anyway, when handshaking with somebody don't grab his hand but instead keep yours spread. As if you're showing 'five'. It's fun watching the other guy/gall's reaction. Kinda mean, though. (That means extra fun points)
Times done: At least once a day
Priceless reactions: You should try it. It cannot be described...
Rating: 9/10

7. Anything with the rabbit
Ah, the rabbit. Source of constant fun. We have an office pet. A rabbit. And... there should be a separate post about him (actually it may be 'her' but we're almost sure it's 'him') with photos and videos.
Rating: 6231/10 ...

?. The singular 'while'
Find some central header file and write "#define while if". Check if it's not included in some source file that has do-while. Watch the other guy debug.
Times done: Never... I made it once at my previous job (guess why it's previous) and it was so great I had to share it here. Unfortunately I made the mistake to share it with my current colleagues. But let's hope that if a new guy comes, he won't have read this blog.
Rating: 10/10

Omit Needless Words (in C++)

I came across a small C++ language feature which I didn't know about. It is a very simple syntactic sugar for omitting needless words. Many of you may already know it but to those who don't I say: read this short blog entry

Omit Needless Words (in C++)


After I shared this with my colleagues I asked them "So can you think of any other situation when the ThisClass typedef in a class is obligatory,... apart from generic programming?" They laughed and said that I had just asked a question "Can something be useful for any other thing than the only one it is useful for?" I was left with my doubts. Can you, readers, prove that wrong? :)

Saturday, September 15, 2007

Named Constructors

Here is a little trick, that all you old-school C++ programmers might not know. Obviously it's called "Named Constructors".

So, suppose you need to make a 3x3 matrix class for your game-math library. You need it to make affine transformations so you have to make it represent rotation and scaling. So here is some code, that you'll probably write:


class matrix3x3
{
public:
   //scaling
   matrix3x3(float xscale, float yscale, float zscale);
   matrix3x3(float uniform_scale);

   //rotation
   matrix3x3(const vec3& axis, float angle);
   matrix3x3(float yaw, float pitch, float yaw);

   //other stuff
   //...
};


Great. But wait a minute! We have two constructors that take three floats each. Damn!

Obviously constructs like


matrix3x3 m(3, 1, 2); //wtf is this? Scaling?


...and the pure impossibility of having two constructors with the same signature make this a bad choice.

So, what can you do?
There is an old-school pattern to write external constructors. Like that:


void matrix_scaling(matrix& out, float xscale ...
void matrix_rotation_yaw_pitch_roll(matrix& out ...


That just doesn't look good. Luckily there is a thing called Return Value Optimization, and specifically Named Return Value Optimization or NRVO (try reading that with your mouth full). Basically NRVO is something that allows you to return heavy objects from functions without worying that they'll be copied, which is slow. And game developers don't like slow. They don't even know what slow means. It's either acceptable or not acceptable. Yeah!... Anywho, this is a link to a blog that explains just how cool NRVO is.

And how did we use it to create our named constructors? That's how:


class matrix3x3
{
public:
   static matrix3x3 scaling(float x, float y, float z)
   {
      matrix3x3 ret;
      //fill ret with appropriate stuff...
      return ret;
   }
   //you get the point...
   //...
   //you really get the point. there is no need for more examples.
};


And just look at how neat the code looks with the named constructors.


matrix3x3 m1 = matrix3x3::scaling(1, 2, 3);
matrix3x3 m2 = matrix3x3::rotation_yaw_pitch_roll(1, 2, 3);


Self documenting code at its finest. And no efficiency loss whatsoever.

I should mention that this is a relatively new standart feature and if you use retro compilers (less than vc8 or less than gcc4) you most probably will suffer from efficiency loss. So hurry and get something contemporary.

If you don't want to bother and read the link I posted above and just want to see whether your compiler has NRVO (I keep reading it "nervo" in my head... that's not right), just test this:


struct nervo //hehe
{
   nervo() : n(23) { cout << "hello world, baby" << endl; }
   nervo(const nervo& s) : n(s.n) { cout << "cloned!!!111one" << endl; }
   ~nervo() { cout << "lights getting dim..." << endl; }
   int n;
};

nervo test()
{
   nervo n;
   return n;
}

...

nervo x = test();

If there's no text like the one from the copy-constructor, you're good to go!

Friday, September 14, 2007

Our Predicated Construction Library

Introducing our predicated construction library that eases conditional usage of sentry (RAII) classes.

Motivating example:

Suppose you have a sentry class that enables wireframe rendering mode in some Direct3D context and upon destruction reverts solid fill.


struct WireframeSentry
{
   WireframeSentry(IDirect3DDevice9* device)
   : m_Device(device)
   {
      m_Device->SetRenderState(D3DRS_FILLMODE, D3DFILL_WIREFRAME);
   }

   ~WireframeSentry()
   {
      m_Device->SetRenderState(D3DRS_FILLMODE, D3DFILL_SOLID);
   }

private:
   IDirect3DDevice9* m_Device;
};


The question is - how can you enable wireframe rendering through the sentry if it's optional, as in you want to enable wireframe rendering based on some external predicate. Obviously you can't optionally skip the constructor of a locally instantiated object.

if (renderInWireframe)
   WireframeSentry(device);


We can do so if, for example we provide a second bool parameter in the constructor:

WireframeSentry(IDirect3DDevice9* device, bool reallyEnable=true)

Clearly this solution doesn't scale, and it doesn't attack the problem at hand - how to conditionally create objects *and* reap the fruit of the destructor-on-scope-exit that the compiler guarantees for local objects.

Solution:

Enter predicated construction. Our example will be superceded by:

bool renderInWireframe = ...;
BOOST_PREDICATED_ANONYMOUS_CONSTRUCTOR(renderInWireframe, WireframeSentry, (device));


If renderInWireframe is true then an unnamed object will be created and destroyed on scope exit. Otherwise nothing will happen (save for an 'if').

Link to the code @ Boost vault

Thursday, September 13, 2007

Pilot Post

Good news, everyone! Our blog has started.

We are some of the developers at Masthead Studios and, as you may see, we're developing a MMOG - Earthrise. Currently at the site it's called Earth Rises Again, but that was a working title and the site is just not updated. (Disregard the last sentence if the site says "Earthrise")

We've been working on the game for quite some time, now. But a recent event reminded us that we wanted a dev-blog since almost day one. So here it is.

We know that hardly anyone will read this first post, so here is some vital info that no one should miss.

  • We won't post things about the game that are not to be disclosed (the boss is reading...)
  • We will post stuff around the company (parties, conventions, conferences, etc)
  • We will probably post some interesting technology observations/articles/samples
  • We will post funny stuff. (Yeah! Light space perspective shadow maps are funny as hell!)
  • We won't fucking watch our language (well, not all of us)
  • And... uhm... that's it.
Have fun reading the blog. Even if you don't read this first post.