QML applications on Nokia Belle

After the latest update of "Nu, Pogodi!", I received few negative reviews saying that the game doesn't work. I've tested the game thoroughly on all devices I was able to get my hands on, but I wasn't able to reproduce the error, so I decided to wait until I get more info. Few days ago with the help of one customer I was able to pin down the problem - the game failed to display any UI on new Belle firmware with Qt 4.8.0. I don't have such device myself, but fortunately the great Remote Device Access service allows testing on Nokia 808 PureView with latest Belle firmware. I've reproduced the error, wrote the Nokia Developers Support, and they sent me a very helpful link: Changes in Nokia Belle FP1. One issue listed there caught my eye:

If application does not specify a size for the root QML object and doesn’t use the Qt components Window as root element (Window component should not be used as a child item), it might cause the root window not to be shown.

Solution / Workaround:
Always declare a size for your custom QML root element.

I've checked my main QML file and indeed, I did not set the root element size, instead I've set the resize mode to SizeRootObjectToView and maximized the QDeclarativeView. I think it's the better solution than setting the root element size explicitly, because the display resolution is not the same on all Nokia phones (I'm looking at you, E6). Instead of doing that, I wrapped my entire UI into Window element from Qt Components and lo and behold, my game displayed something, although it wasn't exactly what I expected:

My code locked the screen orientation after loading main QML file, and it looked like the only thing that might cause this problem, so I changed the calls order. On Belle FP1 devices everything worked fine, but this change broke the display on devices with Anna and older Belle firmware:

Wat? The only solution I came up with was creating the utility method for detecting version of Qt during runtime and locking screen orientation after and before loading main QML file, depending on the Qt version. Relevant piece of code:

bool Utils::runtimeQtAtLeast(int major, int minor, int bugfix)
{
    const QStringList v = QString::fromAscii(qVersion()).split(QLatin1Char('.'));
    if (v.count() == 3) {
        int runtimeVersion = v.at(0).toInt() << 16 | v.at(1).toInt() << 8 | v.at(2).toInt();
        int version = major << 16 | minor << 8 | bugfix;
        return version <= runtimeVersion;
    }
    return false;
}

// ...

const bool qt48 = Utils::runtimeQtAtLeast(4,8,0);
QmlApplicationViewer viewer;
if (qt48) {
    viewer.setOrientation(QmlApplicationViewer::ScreenOrientationLockLandscape);
    viewer.setResizeMode(QDeclarativeView::SizeRootObjectToView);
}

viewer.setMainQmlFile(QLatin1String("qml/nupagadi/GameArea.qml"));

if (!qt48) {
    viewer.setOrientation(QmlApplicationViewer::ScreenOrientationLockLandscape);
    viewer.setResizeMode(QDeclarativeView::SizeRootObjectToView);
}

This kind of incompatibility between minor versions of the Qt framework is mind boggling. It makes me think what else did Nokia screw up in Qt 4.8.0 for Symbian and what will they screw up in the next firmware updates. One thing is sure: I'll have a lot of blogging material.

Git killer feature: content tracking

At my current day job I was the first adopter of git and one of the most frequently question I'm asked as "the git guy" is the variation of "why do you use git instead of mercurial?". I usually responded that git was the first distributed VCS I used, and I played for a while with hg and bazaar, but I haven't discovered any significant feature that would make me change my initial choice. Today I have found the case that allows me to give a better answer.

About a month ago I released the Word Judge application - an offline word validator for Scrabble and other word games. Initially I was working only on one version of Word Judge with polish dictionary, so I had one line of code in my git repository:

When polish version was ready, I decided that I might as well release the english version, because it would require only minor changes: changing app icon and dictionary file. It turned out that I also have to change the application package, so both versions of Word Judge could be installed at the same time. The changes were in fact minor, but included a lot of renaming (package name is mirrored by the directory structure) :

Later on I decided to add ads to my application. First, I've added the necessary code to master (i.e. polish) branch:

I switched to english branch, typed 'git merge master --no-commit', and was very surprised to see just a few conflicts in binary files (icons). All the changes made in java code, in the renamed files, were automatically merged. If you still don't get how awesome this is, consider what would I had to do without it:

1. Start the merge
2. Resolve the conflict by selecting "keep deleted files" for every java file changed in the master branch
3. Manually merge every java file from "pl" package and "en" package
4. Delete "pl" package
5. Commit changes

And I would have to do this every single time I port the changes between language branches. It's a tedious and error-prone job, and git automatically (automagically?) does it for me. How cool is that? Mightily cool IMHO. Of course if I add some java files in one branch, I have to do move them to correct package in the other branch (hence the '--no-commit' switch in git command above), but most of the conflicts are caused by binary files.

It's also more common case than you might think, i.e. you don't have to write a dictionary supporting multiple languages to run into it. For example if you have a lite and full version of an app, you have exactly the same situation.

Right now my repository looks like this (or it would look like this if the git gui tools didn't suck, but that's another story):

I can't imagine supporting such structure without automatic merges provided by git, because it tracks content instead of files. And that's the real killer feature that distinguishes git from other DVCS.

The dark side of LINQ: LINQ to SQL on Windows Phone

In case you don't know what's LINQ and you use C#, I suggest you drop everything you do and enlighten yourself. Be warned: when you learn LINQ, you won't be able to work with Java collections (Guava makes them bearable, but barely) or Qt/STL containers without throwing in your mouth every now and then.

Here's tl;dr for the non-enlightened: LINQ is a sane way to query and alter the data. Instead of this:

private void PrintSortedEvenNumbers(IList<int> unfiltered)
{
    List<int> filtered = new List<int>();
    foreach (int i in unfiltered)
        if (i % 2 == 0)
            filtered.Add(i);
    filtered.Sort();
    foreach (int i in filtered)
        Console.Write(i + " ");
}

You can just write this:

private void PrintSortedEvenNumbers(IList<int> unfiltered)
{
    foreach (int i in unfiltered.Where(num => num % 2 == 0).OrderBy(n => n))

        Console.Write(i + " ");
}

This is a trivial example, but the more complicated code, the more benefit you get from using LINQ.

I started using it for operations on collections and XML files and I immediately fell in love with it. Imagine my joy when I learned that Windows Phone 7.1 finally supports local relational database which can be queried through LINQ to SQL!

I've read the tutorial, thought a bit about the application I was writing at the time and decided that I need many-to-many relationship. Oops, that's not supported. Well, it's "kinda" supported, meaning you can create a data structure and insert some data, but when you remove the data the foreign key constraints won't be verified and cascade triggers won't work. I think I can simplify the above statement and just call it "not supported feature".

Fortunately I didn't absolutely had to use many-to-many relationship. It would be nicer and would allow us to relax some constraints, but the current data could be as well represented using a nested one-to-many relationships. I've wrote the code based on aforementioned LINQ to SQL tutorial, wrote the tests, run them and watched in amazement as they fail. After googling a lot and experimenting I was able to make my code work, but it was quite different than the crap they posted on MSDN as tutorial. If you want to use LINQ to SQL, take a look at this code on github.

I spent about two days reading about LINQ to SQL and experimenting with the code and in the end I didn't even had the data structure I wanted to. And we're not talking here about rocket science, the SQLite scheme I needed was something like this:

create table x (id INTEGER PRIMARY KEY AUTOINCREMENT, text STRING);
create table y (id INTEGER PRIMARY KEY AUTOINCREMENT, text STRING);
create table z (id INTEGER PRIMARY KEY AUTOINCREMENT,
                x_id INTEGER NOT NULL,
                y_id INTEGER NOT NULL,
                FOREIGN KEY(x_id) REFERENCES x(id) ON DELETE CASCADE,
                FOREIGN KEY(y_id) REFERENCES y(id) ON DELETE CASCADE);

Which leads me to conclusion: LINQ to SQL for Windows Phone just doesn't work. Consider also the amount of boilerplate code I had to write for simple foreign key relation: in case you didn't looked at the github link that's whooping 80 lines of code for every one-to-many relationship. I don't know, maybe there are some tools that generate this stuff for you, but in this case why does the official tutorial even mention writing the table classes by hand? And where are those tools?

Recently I was also playing with Django which also features an ORM for the model definition.You need the foreign key? You use something called ForeignKey. You need the many-to-many relationship? You use the ManyToManyField. Dirt simple. I'm sure there are some dark corners you have to be aware of, but the basic stuff just works.

Background operations on Windows Phone 7

Few weeks ago I was complaining to another developer that Windows Phone applications cannot perform tasks in background when they are not running. That was true few months ago when I learned about Windows Phone 7.0, but he pointed me to MSDN documentation of new WP 7.1 feature: Background Agents.

I clicked the link with my hopes up, but I was immediately shot down with the highlight on the first page: "Background agents are not supported on 256-MB devices". I proceeded to the overview page and it turned out the highlight from the first page was just the tip of the iceberg. The constraints listed there are just staggering.

First there are the registration issues: you can register background task for the next two weeks and after that period your application have to reschedule the task. I'm not sure why do I have to do this, and at the first glance it looks only like a minor nuisance, until you take into account two other constraints: tasks cannot reschedule themselves and there is a hard limit of scheduled periodic tasks, which can be ridiculously low. Relevant quote from MSDN:

To help maximize the battery life of the device, there is a hard limit on the number of periodic agents that can be scheduled on the phone. It varies per device configuration and can be as low as 6.

Not a minor nuisance anymore, huh?

This limit is only imposed on periodic agents, which are intended for short, periodic tasks like polling some service or uploading a data. There are also Resource Intensive Agents which can be used for longer tasks like data synchronization, but they have their own set of constraints: the device have to be charging, the battery have to be almost fully charged and there should be a Wi-Fi or PC connection (no cellular data). I think the MSDN note summarizes it quite well:

Due to the constraints on the device that must be met for resource-intensive agents to run, it is possible that the agent will never be run on a particular device. (...)Also, resource-intensive agents are run one at a time, so as more applications that use resource-intensive agents are installed on a device, the likelihood of an agent running becomes even less. You should consider this when designing your application.

I'm going to add to the comment above my own observation: every application can register only one background agent, which can be both periodic agent and resource intensive agent. It means that if you need both types of agents, your resource intensive agent is also affected by the periodic agent hard limit.

It all boils down to this: you can't rely on the background agents. You don't have the guarantee that you'll be able to register the agent, which means that you can't use them for critical functionality. So we're exactly where we were after 7.0 release.

QML error handling revisited

After releasing Nu, Pogodi! I learned the hard way that checking the QML runtime errors might be a good idea. For that particular application, simply checking the errors from QDeclarativeView after setting the main qml file was enough, because everything in qml file was statically declared. But what if you use QML Loader element, either explicitly or through some other qml element like PageStack from Qt Components, and something goes wrong?

Well, if you don't improve the error handling code, your application will silently fail in some places, which probably won't make the users happy. I didn't wanted to repeat the Nu, Pogodi! screw up when releasing Word Judge, so I've created a better error handling solution. First part is an error handler class:

// ----------------------------------------
//  qmlerrorhandler.h
// ----------------------------------------

class QmlErrorHandler : public QObject
{
    Q_OBJECT
public:
    explicit QmlErrorHandler(QDeclarativeView &view, QObject *parent = 0);
    bool errorOccured() const;

private slots:
    void handleQmlStatusChange(QDeclarativeView::Status status);
    void handleQmlErrors(const QList<QDeclarativeError>& qmlErrors);

private:
    QDeclarativeView &mView;
    bool mErrorOccured;

};

// ----------------------------------------
//  qmlerrorhandler.cpp
// ----------------------------------------

QmlErrorHandler::QmlErrorHandler(QDeclarativeView &view, QObject *parent) :
    QObject(parent),
    mView(view),
    mErrorOccured(false)
{
    connect(&view, SIGNAL(statusChanged(QDeclarativeView::Status)), SLOT(handleQmlStatusChange(QDeclarativeView::Status)));
    connect(view.engine(), SIGNAL(warnings(QList<QDeclarativeError>)), SLOT(handleQmlErrors(QList<QDeclarativeError>)));
}

void QmlErrorHandler::handleQmlStatusChange(QDeclarativeView::Status status)
{
    if (status == QDeclarativeView::Error) {
        handleQmlErrors(mView.errors());
    }
}

void QmlErrorHandler::handleQmlErrors(const QList<QDeclarativeError>& qmlErrors)
{
    QStringList errors;
    foreach (const QDeclarativeError& error, qmlErrors) {
        // Special case for bug in QtComponents 1.1
        // https://bugreports.qt-project.org/browse/QTCOMPONENTS-1217
        if (error.url().toString().endsWith("PageStackWindow.qml") && error.line() == 70)
            continue;

        errors.append(error.toString());
    }

    if (errors.isEmpty())
        return;

    mErrorOccured = true;

    QMessageBox msgBox;
    msgBox.setText("Uh oh, something went terribly wrong!");
    msgBox.setInformativeText("We're sorry, but it seems there are some problems "
                              "with running our application on your phone. Please "
                              "send us the following information to help us resolve "
                              "this issue:\n\n") +
                              errors.join("\n"));
    msgBox.exec();
    qApp->exit(-1);
}

bool QmlErrorHandler::errorOccured() const
{
    return mErrorOccured;
}

And here's how I use it in my applications:

int main(int argc, char *argv[])
{
    QScopedPointer<QApplication> app(createApplication(argc, argv));

    QScopedPointer<QmlApplicationViewer> viewer(QmlApplicationViewer::create());
    QmlErrorHandler errorHandler(*viewer);
    viewer->setMainQmlFile(QLatin1String("main.qml"));
    viewer->showExpanded();

    if (!errorHandler.errorOccured()) {
        return app->exec();
    } else {
        return -1;
    }
}

Basically we need to catch the runtime errors, which are emitted from QDeclarativeEngine in signal named for some unfathomable reason "warnings". Checking the errorOccured() in main() is ugly, but the qApp->exit() doesn't work until the event loop in main is started and that's the first thing which came to my mind. Please leave a comment if you know a simpler solution.

Note the lines 46-49 in QmlErrorHandler: we're catching all warnings and the qt components are not completely free of them. I had to add a special case to prevent triggering the handler on every orientation change. If you stumble upon some other errors that should be ignored, please let me know.

Word Judge for Symbian available in Nokia Store

Today I have finally pushed both versions of Word Judge through Nokia Store QA. The version with an english dictionary was available for over the week now, but I had to submit the polish version few times until it passed the Nokia tests.

Anyways, the applications are available for free in Nokia Store. Here's the link for english version:

And for polish version (might not be available in all countries - I had to add some restrictions to pass QA process):

Stay tuned for posts about development of Symbian version and enjoy your Scrabble games.

DAWG data structure in Word Judge

I'm the first to admit that the Word Judge is booooring application. Checking if the word can be used in a word game? Meh. From a programmer perspective however, there is one very interesting problem to solve - how to compress a large dictionary to reduce the size of the application package and at the same time be able to query this dictionary without using excessive amount of memory and CPU power?

First, let's settle on what is a "large dictionary". One of the languages supported by Word Judge is Polish, for which the valid word list has over 2 million entries and takes about 36MB after unpacking. Do we need to compress this data at all? Probably not. If you consider the average hardware spec and modern network speed, the 36MB is not much, but we can do so much better. Besides, it's fun!

One the other end of the spectrum is the "zip all the things" approach. It's not a good idea though - it puts a very heavy load on the CPU and doesn't compress the data that well. The zipped Polish dictionary takes 4.5MB.

The most important observation is that we're not compressing some random white noise, but words from real language. We can leverage this information to get a much better compression than some generic algorithm. Lot of words share the same prefix and suffix, which means they can be efficiently represented as a directed acyclic graph with shared nodes for common prefixes and suffixes. Let's see how the graph would look like for couple of words:

White letters on black background mark the nodes representing the ends of words. So the graph above represents the following words:

abject
abjection
abjections
abjectly
abjectness
ablate
ablated
ablation
ablations

The nodes for 'ab' prefix are of course shared, the 'ions', 's' suffixes nodes as well. For obvious reasons we cannot share the 't' node: in one group it marks the end of the word, in other it does not; the child nodes for each 't' nodes are also different. Nodes are equal, and thus can be shared, if and only if they represent the same letter, the End Of Word flag is the same for both of them, and the list of children is exactly the same.

This type of graph contains minimal number of nodes, but each node takes quite a lot of space. We need 8 bits for the letter, 1 bit for EOW flag, 8 bits for the children list length and some kind of reference, for example node index, to each child, which is log2(n) rounded up bits, where n is a number of nodes in the graph. As you can see the major contributor to a single node size is the children list: for TWL06 dictionary the number of nodes is in the 10k-100k order of magnitude, which means we need several bits per node index.

A guy called John Paul Adamovsky found a neat solution to that. Instead of keeping the full list of children, we can keep children in something similar to singly-linked list: let's store only the index of the first child, number the nodes in such way that the children always have consecutive indices and add a End Of Children List flag to each node. This way we need exactly 1 + log2(n) bits for child list. This way we can keep the entire node in one byte. What's the catch? We need to introduce few more nodes.

For example on the graph above we can no longer share the 'i' node in the 'ions' suffix: if it was shared it would have to have a number one greater than the number of both 'e' node in 'ablate' and 'n' node in 'abjectness' (this is, of course, assuming the 'i' node is the last on the child list of both 't' nodes; but it's impossible for any node ordering). Our graph would look like this:

The rule for node equality has to be extended: the nodes are equal if they represent the same letter, the flags are the same, the children are equal and the siblings further on the children list are equal. The last condition is a bit confusing, so I'll provide an example.

Let's add a 'absolution' and 'absolutions' to our dictionary. We can certainly share the 'ab' prefix and 'ons' suffix, but do we need a separate 'i' node as well? The 'i' node in 'absolution' must have a End-Of-Child-List flag set. If we arrange the child nodes in either 'ablat-' or 'abject-' part of graph in such way that the 'i' node is the last node, we can share the 'i' node between that part of graph and the newly added branch. Our graph would look like this:

This is the way we can squeeze the 36MB dictionary to 1.5MB. The structure also doesn't need any processing, it can be loaded to int array and used directly. If you're curious how to convert the dictionary into this kind of graph you can read the description of my dawggenerator project on github (C++) or the original description by John Paul Adamovsky (pure C).