Descend 0.2 released

Submitted by mimec on 2012-10-15

The first official version of Descend was released today. You can grab it from the Descend website which was also officially launched today. It's quite a historical moment, as Descend has been waiting for about eight years to be released. You can read a short history of this program and its predecessors here. Also this is the fourth sub-website in the family, so I decided to add some nice links on the front page.

What's coming next? As I said recently, I have plans to start working on version 1.1 of WebIssues, but before I release the first beta version, you can also expect new releases of both Saladin and... Fraqtive. Possibly by the end of this year :).



Submitted by mimec on 2012-10-08

It's been a while since I last wrote a post, but I've been quite busy. First of all, in a week or two I will release the first, official beta version of Descend. It will be quite an event, because I made several attempts at writing it in the last eight years and I've never come that close to finishing it. In case you missed the earlier post about Descend, it's a program for drawing 3D surfaces (and curves) based on parametric equations. It's sort of a conceptual project, so it's not going to have a lot of features, but it aims at being very fast and producing high quality graphics.

Another thing that has been bugging my mind in the past few months is the future of WebIssues. I came to the point where it simply doesn't make a lot of sense to put more effort into it without actually getting something back. I made lots of analysis how to make money from this project, especially focusing on controversies around the open core model. I came to the conclusion that the best solution is to create a specialized, commercial system based largely on WebIssues and dedicated to a narrow group of users, while keeping WebIssues itself a free, powerful, general purpose tool for bug tracking, project management, etc., which it already is, and letting it continue to evolve.

The idea is not new; I've been thinking about profiting from WebIssues since I started working on version 1.0 three years ago, but now I have a much clearer vision of what I'm trying to achieve. Most of all, I don't want to be an outsourced developer for the rest of my life. I got as far as I could in this area in terms of both allowance and career development. I need to change something sooner or later and this could be a great opportunity to do that. Of course, I could just get a highly paid job and forget about all this open source shenanigans; but in the end, what you achieve in life is a matter of much more than just money. So as always I'm choosing the harder way, and it's going to take time, but I think it's going to be worth the effort.

At the moment, however, I'm already planning to start working on version 1.1. The updated roadmap includes a long description field, roles and groups, LDAP authentication and project summary. I have an initial design for some of these features, others may be added as well, the roadmap is not closed yet. I will be posting more information on and might even release the first beta version by the end of the year, but I'm not enforcing any deadlines on me. As long as I do it for free, it's nothing more than a hobby, and as such it competes for my time with other hobby projects, including Descend, Saladin, and especially the new update for Minecraft: Xbox 360 Edition that's coming out soon :).

Serialization in Qt - part 4

Submitted by mimec on 2012-08-22

I the last few posts I wrote about serializing data in an extensible and effective binary format using QDataStream. So far it was focused on value types and simple structures that can be easily converted to QVariant and QVariantMap. In the last post I mentioned that creating objects dynamically based on class name requires implementing some kind of an object factory. Now let's analyse what is needed to serialize an entire hierarchy of abstract objects that refer to one another. Note that this is a very complex topic and there is no single, universal solution, so I won't provide the full code. Instead I will discuss what is necessary to craft such solution depending on the exact requirements.

Let's assume that we're serializing a project which consists of shapes of various types - circles, squares, etc. There are also some complex shapes, like groups or layers, which consist of other shapes. The first difficulty is that shape is an abstract type, so we need to store the actual class name along with the object data in order to be able to re-create the object upon deserialization. This was more or less covered in the last post.

Another difficulty is that objects refer to one another by pointers, forming a graph of relations, in which one object may be accessed from many other objects. We need to ensure that the object is only serialized and deserialized once, and all other references must be correctly maintained. There even can be cyclic dependencies; for example a parent object can have a pointer to a child, and the child can have a pointer to the parent.

For sake of simplicity I will assume that each serializable class inherits QObject; that's not really necessary, but having a single common base class makes things easier. The class should also be registered in the object factory discussed before. Finally, it should implement the following interface, which provides methods for serializing and deserializing the object:

class Serializable
    virtual void serialize( QVariantMap& data, SerializationContext* context ) const = 0;
    virtual void deserialize( const QVariantMap& data, SerializationContext* context ) = 0;

The data is stored in a QVariantMap for reasons that were also discussed in one of the previous articles, so that the file format is extensible and backward compatible. The context object is responsible for performing the serialization and deserialization. We will get to it in a moment.

Note that the Serializable class could be an abstract class which inherits QObject. All concrete classes could then inherit it and implement the serialization methods. However, in this case it wouldn't be possible to add serialization capabilities to existing subclasses of QObject, for example widgets. Using a separate interface gives us more flexibility. Although multiple inheritance in C++ is a very complex subject, it's very common in most object oriented languages for a class to inherit behavior and implementation from a single base class, and implement a number of additional interfaces.

An incomplete example of a serializable class containing a pointer might look like this:

class Shape : public QObject, public Serializable
    void serialize( QVariantMap& data, SerializationContext* context ) const
        data[ "Name" ] << m_name;
        data[ "Other" ] = context->serialize( m_other );

    void deserialize( const QVariantMap& data, SerializationContext* context )
        data[ "Name" ] >> m_name;
        m_other = context->deserialize<Shape>( data[ "Other" ] );

    QString m_name;
    Shape* m_other;

The serialize method of the SerializationContext first checks if the given object was already serialized. If not, it appends it to the internal list of objects and calls the serialize method on this object to store its data in a QVariantMap. Then it returns a handle to the object, which is a QVariant. Internally it contains an integer value identifying the object in the given context.

The deserialize method checks if the object with the given handle was already deserialized. If not, it creates a new instance of the appropriate class using the object factory and calls the deserialize method. Note that the object is not necessarily a Shape; it might actually be a subclass of it like Square or Circle.

Note that the context doesn't actually read or write any data from/to a stream. Instead, it stores a list of records, which include the pointer to the object, its class name and serialized data. So the handle is simply the position of the object in the list. The entire context can be written into the stream once all objects are serialized. Conversely, when deserializing, the context is first read from the stream, and then individual objects are deserialized.

We may serialize as many objects as we need using the same context, but we need to store the handles in the stream along with the context data, because we will need them when deserializing. Alternatively, we may serialize an entire hierarchy of objects by serializing the "root" object and ensuring that all children are serialized recursively:

QDataStream stream;
SerializationContext contex;

context.serialize( root );

stream << context;

In that case we don't need to store the handle, because we know that the handle of the first serialized object is always integer zero (not to be confused with invalid variant, which represents a NULL pointer):

QDataStream stream;
SerializationContext contex;

stream >> context;

Shape* root = context.deserialize<Shape>( QVariant::fromValue<int>( 0 ) );

So what does the SerializationContext class look like? This is an incomplete definition:

class SerializationContext
    template<typename T>
    QVariant serialize( T* ptr );

    template<typename T>
    T* deserialize( const QVariant& handle );

    friend QDataStream& operator <<( QDataStream& stream, const SerializationContext& context );
    friend QDataStream& operator >>( QDataStream& stream, SerializationContext& context );

    struct Record
        QObject* m_object;
        QByteArray m_type;
        QVariantMap m_data;

    QList<Record> m_records;
    QHash<QObject*, int> m_map;

The serialize and deserialize methods are discussed below. The shift operators make it possible to read and write the entire context from/to the stream. The list of records stores information about objects, including their type and data. The map is optional; it simply makes lookup slightly faster for a large number of objects.

You can notice that both the serialize and deserialize methods are templates. Why not simply cast everything to void*? Also why the record and the map stores a QObject*, instead of a void*?

This is because of how multiple inheritance works in C++. Let's assume that you have a pointer to a Shape object. When you cast it to QObject*, and to Serializable*, you will receive two different pointers, that may be different from the original one. That's because in memory, the Shape object consists of a QObject, followed by Serializable, so an offset must be added or subtracted to convert one pointer to another.

You can safely cast pointers up and down the hierarchy of classes using the static_cast operator, and the compiler will ensure behid the scenes that the pointers are adjusted accordingly. But when you cast something to void*, you lose all the information, so casting it back to some other pointer may produce wrong results!

Let's take a look at the serialize method:

template<typename T>
QVariant SerializationContext::serialize( T* ptr )
    if ( ptr == NULL )
        return QVariant();

    QObject* object = static_cast<QObject*>( ptr );

    QHash<QObject*, int>::iterator it = m_map.find( object );

    if ( it != m_map.end() )
        return QVariant( it.value() );

    int index = m_records.count();

    Record record;
    record.m_object = object;
    record.m_type = object->metaObject()->className();
    m_records.append( record );

    m_map.insert( object, index );

    Serializable* serializable = static_cast<Serializable*>( ptr );

    QVariantMap data;
    serializable->serialize( data, this );

    m_records[ index ].m_data = data;

    return QVariant( index );

Notice how the pointer is explicitly casted to QObject*, and later it's casted to Serializable*? It's not possible to cast a QObject* to Serializable*, because they are unrelated classes, and forcing the cast by using reinterpret_cast or casting to void* would certainly crash the application. This is even more apparent in the deserialize method:

template<typename T>
T* SerializationContext::deserialize( const QVariant& handle )
    if ( !handle.isValid() )
        return NULL;

    int index = handle.toInt();

    Record& record = m_records[ index ];

    if ( record.m_object != NULL )
        return static_cast<T*>( record.m_object );

    QObject* object = ObjectFactory::createObject( record.m_type );

    record.m_object = object;

    m_map.insert( object, index );

    T* ptr = static_cast<T*>( object );
    Serializable* serializable = static_cast<Serializable*>( ptr );

    serializable->deserialize( record.m_data, this );

    return ptr;

Here the QObject* is first casted "up" to the actual type, T*, and then "down" to Serializable*. It doesn't matter if T is a Shape and the object is actually a Square or Circle, because all subclasses of Shape have the same layout of base classes.

Other than that, the code is quite straightforward, though there is another gotcha when dealing with circular references between objects. The record must be appended to the list before the serialize method is called on the object. This way, if the same pointer is encountered while serializing the object, it is not serialized again, which would lead to infinite recursion.

Object factory

Submitted by mimec on 2012-07-26

Before I continue the series about data serialization in Qt, there is one important related topic than needs to be mentioned first: the ability to dynamically create an object based on a class name.

Let's assume that we want to serialize a list of shapes. The Shape is an abstract class and actual objects stored in the list have various derived classes: Rectangle, Circle, etc. During serialization, we can save the class name and the object data for each item. During deserialization, we need to be able to create an instance of an appropriate class. This is where an object factory becomes necessary. In languages like C# or Java, which support reflection, it is possible to instantiate a class given as a string with a few lines of code. But in C++ there is no such mechanism.

The simple solution is to create a single function with a large switch (or series of ifs) that creates the object of an appropriate type. It's not particularly elegant and it breaks the object oriented design, but in many cases it's acceptable. However, when you have lots of classes that are scattered through different parts of the application, it may become hard to manage. And if the application has external modules or dynamically loaded plug-ins, it becomes even more difficult.

A much more elegant solution is when the factory is abstract and it doesn't know anything about the objects it creates. Instead, classes that can be instantiated using the factory have to be registered using some type of internal map. This way, each module or plug-in can independently register its own set of classes.

Qt has two mechanism that can be useful for creating such factories. They may seem similar, but in fact there are major differences.

The construct() method can be used to create an instance of any built-in type, or a custom type for which the Q_DECLARE_METATYPE macro was specified. This is what a QVariant does internally to wrap an custom type. However, this mechanism is designed to be used for value types, i.e. classes that have default constructors and copy constructors. It doesn't make any sense for objects of abstract classes, which are almost always passed by pointer, and often have their copy constructors disabled.
The newInstance() method can be used to create an instance of any class that inherits QObject. The only condition is that the constructor needs to be explicitly declared with the Q_INVOKABLE modifier. This works fine with polymorphic objects, because QObject is often used as a base class for various abstract hierarchies of classes (for example widgets). Note that since Qt 4 it is not possible to retrieve a QMetaObject based on the class name without some additional work.

It is very easy to create an object factory which relies on QMetaObject. An example can be seen here. However, this solution has a few disadvantages:

  • The constructor needs to be explicitly declared with Q_INVOKABLE in order to be accessible from the QMetaObject.
  • There is no compile time check whether the appropriate constructor exists and is accessible, or whether parameter types are correct. You will only get a runtime warning when you actually try to create the instance and NULL will be returned instead.
  • Subclassing QObject adds some memory footprint to each object instance. Also dynamic method calls used by QMetaObject have some overhead as run-time type checking has to be performed.

However it's not difficult to create a custom factory for classes of any type, that doesn't have these limitations. An example of a custom factory that works for any class that inherits QObject can be seen below:

class ObjectFactory
    template<typename T>
    static void registerClass()
        constructors().insert( T::staticMetaObject.className(), &constructorHelper<T> );

    static QObject* createObject( const QByteArray& className, QObject* parent = NULL )
        Constructor constructor = constructors().value( className );
        if ( constructor == NULL )
            return NULL;
        return (*constructor)( parent );

    typedef QObject* (*Constructor)( QObject* parent );

    template<typename T>
    static QObject* constructorHelper( QObject* parent )
        return new T( parent );

    static QHash<QByteArray, Constructor>& constructors()
        static QHash<QByteArray, Constructor> instance;
        return instance;

With this approach, there is no need to declare the constructor with Q_INVOKABLE. Also, if no appropriate constructor is found, a compile-time error will be reported in the constructorHelper() method as soon as the class is registered. This code is very easy to use:


// ...

QObject* foo = ObjectFactory::createObject( "Foo" );

It is also easy to modify this code so that it works for custom abstract class hierarchies that do not inherit QObject. For example, instead of using the class name retrieved from the QMetaObject as a key, it can use a key of any type that is passed to the registerClass() method or retrieved automatically from a static class member. Also a different set of parameters can be passed to the constructor depending on the needs.

Serialization in Qt - part 3

Submitted by mimec on 2012-07-16

In the previous post I already wrote about backward and forward compatibility when serializing and deserializing data into a binary stream. Let's summarize:

  • backward compatibility - the ability to deserialize data serialized by and older version of the application
  • forward compatibility - the ability to deserialize data serialized by a newer version of the application

I said that backward compatibility can be achieve by storing a version tag in the data stream and conditionally changing the deserialization routine based on the version of data. However forward compatibility cannot be achieved this way because we can't predict what changes will be made in the future. This is fine for configuration data, but in case of documents it's not always acceptable.

The best solution would be to allow the application to skip and ignore information it doesn't understand, and extract as much information as it can. Note that it's not always possible. In case of a text document, the content can be preserved even if some fancy formatting is lost. However, let's recall the example in which we added child bookmarks to the Bookmark class. Even if we could skip loading the child bookmarks, we would still lose a lot of information, as only the top level bookmarks would be available in the old version. So before we start thinking about a fancy solution, we should first ask ourserlves if it's really worth the effort.

There is also a relatively simple workaround available. The new version of the application can be forced to save data in format compatible with an older version. This simply means that we have to add similar conditional code in serialization routines. Many applications work in this way, including MS Office applications. For example, the application could save all bookmarks in a linear fashion, losing the parent-child relationship, but still preserving all bookmarks.

But for true compatibility we need to design the data format in such way, that when the application encounters data that it doesn't understand, it can at least skip it and continue processing. But without additional metadata the application doesn't even know how many bytes it should skip.

A simple solution is to wrap all data in a QVariant before serializing, because QVariant writes a tag which identifies the type of the data before the actual data. Let's start with the following code:

template<typename T>
void operator <<( QVariant& data, const T& target )
    data = QVariant::fromValue<T>( target );

template<typename T>
void operator >>( const QVariant& data, T& target )
    target = data.value<T>();

These are generic function templates that convert any data to and from a variant. Now let's specialize these functions for our Bookmark type from the previous post. We will use a map to convert a bookmark to a variant and vice versa:

void operator <<( QVariant& data, const Bookmark& target )
    QVariantMap map;
    map[ "Name" ] << target.m_name;
    map[ "URL" ] << target.m_url;
    map[ "Children" ] << target.m_children;
    data << map;

void operator >>( const QVariant& data, Bookmark& target )
    QVariantMap map;
    data >> map;
    map[ "Name" ] >> target.m_name;
    map[ "URL" ] >> target.m_url;
    map[ "Children" ] >> target.m_children;

Note that because the bookmark object is converted to a QVariantMap before serializing, it can be successfully deserialized even if the application that reads the data doesn't know anything about the Bookmark type. What's more, we can add more elements to the map in the future without affecting either backward or forward compatibility. When reading a newer version of the file, the elements which are not understood are simply ignored. When reading an older version, missing elements are automatically replaced with default values for the given type.

When we try to compile the above code, we will receive a cryptic error similar to 'qt_metatype_id' : is not a member of 'QMetaTypeId<T>'. That's because a QList<Bookmark> cannot be converted into a QVariant. Since we know how to convert a Bookmark into a QVariant, we can easily convert a QList<Bookmark> into a QVariantList. This can even be done in a generic way:

template<typename T>
void operator <<( QVariant& data, const QList<T>& target )
    QVariantList list;
    list.reserve( target.count() );
    for ( int i = 0; i < target.count(); i++ ) {
        QVariant item;
        item << target[ i ];
        list.append( item );
    data = list;

template<typename T>
void operator >>( const QVariant& data, QList<T>& target )
    QVariantList list = data.toList();
    target.reserve( list.count() );
    for ( int i = 0; i < list.count(); i++ ) {
        T item;
        list[ i ] >> item;
        target.append( item );

This way any QList<T> can be converted from/to a QVariant as long as T can be converted from/to a QVariant. Note that we may also want to create additional specializations for QStringList and QVariantList, so that they are not unnecessarily converted, and to add similar conversion functions for maps and other containers.

To summarize, the following conversions are used before data is serialized:

  • Primitive types (numbers, strings and many other built-in types in Qt) are stored as QVariant
  • Objects are stored as QVariantMap that maps properties to values
  • List of various types are stored as QVariantList

The actual serialization consists of two steps: converting the serialized object into a QVariant and serializing the converted data into the stream. Deserialization is analogous and works in the opposite way.

You can notice that the converted data is somewhat similar to the DOM tree of XML document. A variant of a primitive type is analogous to a leaf XML node, and a map of variants is similar to an XML element with child nodes. However, this approach is more compact, faster and easier to use than XML.

Note that simple custom types don't necessarily have to be stored as a QVariantMap. For example, in a financial application, there may be a Money class, which is really a wrapper over some simple numeric value. We can directly place this numeric value in a variant (e.g. as a qlonglong) without wrapping it in a map.

We can also combine the method of serialization based on QVariantMap with the traditional approach, as described in the previous article, for certain types that highly unlikely to change, and can be treated as primitive types. For example, in a graphic application we might define a Circle class which consists of a central QPoint and a radius. We can use the Q_DECLARE_METATYPE macro and the qRegisterMetaTypeStreamOperators function, so that the Circle object can be directly wrapped into a variant and serialized without any conversions.

Just remember that when the Circle type is introduced in a later version of the application, previous versions will not be able to load a file that contains it, so we must remeber about the version tag, as described in the previous post. Also the version of the data format used by built-in Qt types is important to maintain compatibility across different environments.