Bug hunting fun with std::sort

Small errors in custom comparison functions used with std::sort can lead to hard-to-find bugs.

The other day I came across a nice little C++-shoot-yourself-in-the-foot at one of our customers. Let’s see how fast you can spot the problem. The following code crashes with segmentation fault sometime, somewhere in the sort call (line 31).

#include <iostream>
#include <vector>
#include <boost/shared_ptr.hpp>
#include <boost/bind.hpp>

using namespace std;
using namespace boost;

enum SORT_ORDER
{
  SORT_ORDER_ASCENDING,
  SORT_ORDER_DESCENDING
};

bool compareValues(const std::string& valueLeft,
                   const std::string& valueRight,
                   SORT_ORDER order)
{
  const bool compareResult = (valueLeft < valueRight);
  if (order == SORT_ORDER_DESCENDING) {
    return !compareResult;
  }
  return compareResult;
}

int main(int argc, char *argv[])
{
  std::vector<std::string> strValues(300);
  std::fill(strValues.begin(), strValues.end(),
            "Hallo");
  std::sort(strValues.begin(), strValues.end(),
            bind(compareValues, _1, _2, SORT_ORDER_DESCENDING));
  return EXIT_SUCCESS;
}

Any ideas? The tricky thing about this bug is that the stacktrace output in the debugger gives absolutely no hint at all about its cause. And this is a simplified version of the real code which has to sort boost::shared_ptrs instead of strings. Believe me, you don’t want to see that stacktrace. Because of the use of boost::bind together with boost::shared_ptrs it looks, well, let’s say intimidating.

Still no idea?

I’ll give you a hint. If the SORT_ORDER is set to SORT_ORDER_ASCENDING everything is fine. …

Ok, the problem is that std::sort algorithm must be given a comparison function (object) that defines a strict weak ordering on the elements that are to be sorted. In other words the comparison function object must implement the ‘<‘ (less than) relationship on the elements.

Unfortunately, lines 20 to 22 break this ordering when SORT_ORDER_DESCENDING is given. The initial idea of this code was that, well, if compareResult gets returned on ascending sort order, lets just return the negation of it when the “negation” of acscending order is requested. This, of course, destroys the strict weak ordering requirement because whenever valueLeft == valueRight, the function returns true, meaning instead that valueLeft < valueRight. And this somehow wreaks havoc inside std::sort.

A better version of the function could be:

...
bool compareValues(const std::string& valueLeft,
                   const std::string& valueRight,
                   SORT_ORDER order)
{
  // solution: return false independent of sort order
  // whenever valueLeft == valueRight
  if (valueLeft == valueRight) {
    return false;
  }
  const bool compareResult = (valueLeft < valueRight);
  if (order == SORT_ORDER_DESCENDING) {
    return !compareResult;
  }
  return compareResult;
}
...

The really annoying thing about this whole issue is that std::sort just randomly crashes with a stack trace that shows nothing but some weird memory corruption going on. After the initial shock, this sends you down the complete wrong bug hunting road where you start looking for spots where memory could be overwritten or the like.

So beware of custom comparison functions or function objects. They might look innocent and easy, but they can give you lot’s of headaches.

Developing Grails Apps – Some Dark Sides

Most of the time, developing Grails apps is a nice experience. But there are also dark sides. One of which is when bugs do appear or do not appear depending on how you started your app.

Usually, I try to avoid it but this time a Disclaimer is in order: This is not a Grails rant. Most of the time developing Grails projects is fast and smooth. Using Grails brought many advantages for us. But there are also dark sides…

My main criticism is that Grails abstractions are more than leaky! In every list of examples for the definition of the term Leaky Abstraction Grails should be top. As soon as you leave the tutorial/scaffolding/helloworld level you have to know a lot about the underlying stack. And with Hibernate and Spring neither of the words small, easy and lightweight do apply.

GORM, too, is only easy to use at first sight. The very informative blog series about GORM gotchas should absolutely become part of the user guide or the refence docs.

And there are those times where it gets really unpleasant. This is e.g. when a bug does appear in your grails application running in a servlet container (packaged in a .war)  but does not appear when the application is started from within the IDE. Our last one of those was a naming conflict in a .gsp file. The controller handed a model like this to the .gsp:

...
return [fieldValue: 'THE_VALUE', ...]

The model entry ‘fieldValue’ was used in the .gsp to set the value of a combo box. Unfortunately, ‘fieldValue’ is also the name of a built-in Grails tag

Admittedly, ‘fieldValue’ was not the wisest choice of names and I would certainly expect to get scolded loudly by Grails for that – ideally with a nice descriptive exception. But what happend instead led to a loud scolding of Grails from us. And to some big question marks: What is the difference between executing Grails from the IDE and within a servlet container with respect to naming resolution? Why is there a difference, at all?

We had a hard time figuring out this one, not least because the error message was not very telling. And since this was not the first of those works-in-the-IDE-but-not-in-a-real-environment bugs there is always this slightly uneasy feeling…

As I said in the beginning, most of the time developing Grails applications is nice and shiny. I would not support their slogan, though. My personal search for the best web development tool is definitively not over.

How about your search?

Responsive Qt GUIs – Threading with Qt

Qt4 used to have only primitive threading support. Starting with version 4.4 new classes and functions makes your threading life a lot easier. So in case you haven’t come around to look at those features, do it now!, it’s worth it.

If you have used Qt4 for some time now, specifically since pre 4.4 versions, you may or may not aware of the latest developments in the threading part of the library. This post shall be a reminder in case you didn’t follow the versions in detail or just didn’t get around to look closer and/or update.

In pre 4.4 versions, the only way to do threading was to use class QThread. Subclass QThread, implement the run method, and there you had your thread. This looks fine at first, but, taking the title of the post as example, it can get annoying very fast. Sometimes you have just few lines of code you want to keep away from the GUI thread because, e.g. they could potentially block on some communication socket. Subclassing QThread for every small little work package is not something you want to do, so I guess many users just wrote their own thread pool or the like.

Starting with version4.4. Qt gained two major threading features, for which, IMHO, the Qt people do not a very good job of advertising. The first is QThreadPool together with QRunnable. All Java programmers, which use java.lang.Runnable since the beginning, may have their laugh now, I’ll wait…

The second new threading feature is the QtConcurrent namespace (from the Qt documentation):

The QtConcurrent namespace provides high-level APIs that make it possible to write multi-threaded programs without using low-level threading primitives such as mutexes, read-write locks, wait conditions, or semaphores

Sounds great! What else?

QtConcurrent includes functional programming style APIs for parallel list prosessing, including a MapReduce and FilterReduce implementation for shared-memory (non-distributed) systems, and classes for managing asynchronous computations in GUI applications.

This is really great stuff. Functions like QtConcurrent::run together with QFuture<T> and QFutureWatcher<T> can simplify your threading code significantly. So, if you haven’t got around to look at those new classes by now, I can only advise you to do it immediately. Allocate a refactoring slot in your next Sprint to replace all those old QThread sub-classes by shiny new QRunnables or QtConcurrent functions. It’s worth it!

Let’s get back to the responsive GUIs example. In his Qt Quarterly article, Witold Wysota describes in detail every technical possibility to keep your GUI responsive. It’s a very good article which provides a lot of insights. He starts with manual event processing and mentions the QtConcurrent features only at the very end of the article. I suggest the following order of threading-solutions-to-consider:

  1. QtConcurrent functions
  2. QThreadPool + QRunnable
  3. rest

Stay responsive!

Non-trivial Custom Data in QActions

If you want to implement dynamic context menus with non-trivial custom data in your QActions, the Qt4 documentation is not very helpful. The article describes some solutions to this task.

Sometimes I get very frustrated with the online Qt4 documentation. Sure, the API docs are massive but for many parts they provide only very basic information. Unfortunately, many Qt books, too, often stop exactly at the point where it gets interesting.

One example for this are context menus. The API docs just show you how menus in general are created and how they are connected to the application: Basically, all menus are instances of QMenu which are filled with instances of QAction. QActions are used as representation of any kind of action than can be triggered from the GUI.

The standard method to connect QActions to the GUI controlling code is to use one of their signals, e.g. triggered(). This signal can be connected to a slot of your own class where you can then execute the corresponding action. This works fine as long as you have a limited set of actions that you all know at coding time. For example, a menu in your tool bar which contains actions Undo/Redo/Cut/Copy/Paste can be created very easily.

But there are use cases where you do not know in advance how many actions there will be in your menus. For example, in an application that provides a GUI for composing a complex data structure you may want to provide the user assisting context menus for adding new data parts depending on what parts already exist. Suddenly, you have to connect many actions to one slot and then you somehow have to know which QAction the user actually clicked.

Btw, let’s all recall the Command Pattern for a moment… ok, now on to some solutions.

Method 0 – QAction::setData: The QAction class provides method setData(), which can be used to store custom data in a QAction instance using QVariant as data wrapper. If you then use QMenu’s triggered signal, which gives you a pointer to the QAction that was clicked, you can extract your data from the QAction. I find this a little bit ugly since you have to wrap your data into QVariant which can get messy, if you want to provide more than one data element

Method 1 – Enhancing QAction::triggered(): By sub-classing QAction you can provide your own triggered() signal which you can enhance with all parameters you need in your slot.

class MyAction : public QAction
{
  Q_OBJECT
  public:
    MyAction(QString someActionInfo)
      : someActionInfo_(someActionInfo)
    {
      connect(this, SIGNAL(triggered()),
              this, SLOT(onTriggered()));
    }
  signals:
    void triggered(QString someActionInfo);
  private slots:
    void onTriggered() {
      emit triggered(someActionInfo_);
    }
  private:
    QString someActionInfo_;
};

This is nice and easy but limited to what data types can be transported via signal/slot parameters.

Method 2 – QSignalMapper: From the Qt4 docs on QSignalMapper:

This class collects a set of parameterless signals, and re-emits them with integer, string or widget parameters corresponding to the object that sent the signal.

… which is basically the same as we did in method 1.

Method 3 – Separate domain specific action classes: By the time the context menu is created you add QActions to the menu using QMenu’s addAction methods. Then you create instances of separate Command-like classes (as in Command Pattern) and connect them with the QAction’s triggered() signal:

// Command-like custom action class. No GUI related stuff here!
class MySpecialAction : public QObject
{
  Q_OBJECT
  public:
    MySpecialAction(QObject* parent, &lt;all necessary parameters to execute&gt;);

  public slots:
    void execute();
  ...
};

// create context menu
QAction* specialAction =
  menu-&gt;addAction(&quot;Special Action Nr. 1&quot;);
MySpecialAction* mySpecialAction =
  new MySpecialAction(specialAction, ...);
connect(specialAction, SIGNAL(triggered()),
        mySpecialAction, SLOT(execute()));

As you can see, QAction specialAction is parent of mySpecialAction, thereby taking ownership of mySpecialAction. This is my preferred approach because it is the most flexible in terms of what custom data can be stored in the command. Furthermore, the part that contains the execution code – MySpecialAction – has nothing at all to do with GUI stuff and can easily be used in other parts of the system, e.g. non-GUI system interfaces.

How have you solved this problem?

The C++ Shoot-yourself-in-the-Foot of the Week

I think we can all agree that C++, compared to other languages, provides quite a number of possibilities to screw up. Everybody working with the language at some point probably had problems with e.g. its exception system, operator overloading or automatic type conversions – to name just a few of the darker corners.

There are also many mitigation strategies which all come down to ban certain aspects of the language and/or define strict code conventions. If you follow Google’s style guide, for example, you cannot use exceptions and you are restricted to a very small set of boost libs.

But developers – being humans – often find creative and surprising ways to thwart every good intentions. In an external project the following conventions are in place:

  • Use const wherever you possibly can
  • Use boost::shared_ptr wherever it makes sense.
  • Define typedefs to shared_ptrs  in order to make code more readable.
  • typedefs to shared_ptrs are to be defined like this:
typedef boost::shared_ptr&lt;MySuperDuperClass&gt; MySuperDuperClassPtr;
  • typedefs to shared const pointers are to be defined like this:
typedef boost::shared_ptr&lt;const MySuperDuperClass&gt; MySuperDuperClassCPtr;

As you can see, postfixes Ptr and CPtr are the markers for normal shared_ptrs and constant shared_ptrs.

Last week, a compile error about some const to non-const conversion made me nearly pull my hair out. The types of variables that were involved all had the CPtr postfix but still the code didn’t compile. After a little digging I found that one of the typedefs involved was like this:

typedef boost::shared_ptr&lt;  MySuperDuperClass&gt; MySuperDuperClassCPtr;

Somebody just deleted the const modifier in front of MySuperDuperClass but left the name with the CPtr untouched. And because non-const to const conversions are allowed this was not detected for a couple of weeks. Nice going!

Any suggestions for a decent style checker for c++? Thanks in advance 😉

Improved Version of CMake Builder for Hudson

Introducing version 1.5 of cmake builder plugin for Hudson.

Today I just want to give a small round-up of the improvements made on the cmake builder plugin since my last blog post. Back then, version 1.2 was released to support master/slave configurations. As of yesterday, we are at version 1.5 which contains the following improvements/bug-fixes:

  • Bug: The drop-down box for selecting the build type didn’t remember its value. This was fixed with a patch by Atte Timonen.
  • Improvement: Also included in Atte’s patch was the propagation of environment variables to the cmake command which now allows to do parameterized builds. A big thank’s to Atte!
  • Improvement: The install command gets only executed when install directory and install command is given. Before, the build was either broken or $WORKSPACE was used automatically as install directory. Thanks to Dat Chu for his feedback.
  • Improvement: The one-line ‘Other CMake Arguments’ field can get full pretty quickly, so it was changed to a multi-line text-area.

Thank’s again for the feedback, and have fun with the new version!

Wrestling with Qt’s Model/View API – Filtering in Tree Models

Qt4’s model/view API can be kind of a challenge sometimes. Well, prepare for a even harder fight when sorting and filtering come into play.

As I described in one of my last posts, Qt4’s model/view API can be kind of a challenge sometimes. Well, prepare for a even harder fight when sorting and filtering come into play.

Let’s say you finally managed to get the data into your model and to provide correct implementations of the required methods in order for the attached views to display it properly. One of your next assignments after that is very likely something like implementing some kind of sorting and filtering of the model data. Qt provides a simple-at-first-sight proxy architecture for this with API class QSortFilterProxyModel as main ingredient.

Small preliminary side note: Last time I checked it was good OO practice to have only one responsibility for a given class. And wasn’t that even more important for good API design? Well, let’s not distract us with such minor details.

With my model implementation, none of the standard filtering mechanisms, like setting a filter regexp, were applicable, so I had to override method

QVariant filterAcceptsRow ( int source_row, const QModelIndex& sourceParent ) const

in order to make it work. Well, the rows disappeared as they should, but unfortunately so did all the columns except the first one. So what to do now? One small part of the documentation of QSortFilterProxyModel made me a little uneasy:

“… This simple proxy mechanism may need to be overridden for source models with more complex behavior; for example, if the source model provides a custom hasChildren() implementation you should also provide one in the proxy model.”

What on earth should I do with that? “… may need to be overridden“? “… for example.. hasChildren()…” Why can’t they just say clearly what methods must be overridden in which cases???

After a lot more trial and error I found that for whatever reason,

int columnCount ( const QModelIndex& parent ) const

had to be overridden in order for the columns to reappear. The implementation looks like what I had thought the proxy model would do already:

int MyFilter::columnCount ( const QModelIndex& parent ) const
{
   return sourceModel()->columnCount(parent);
}

So beware of QSortFilterProxyModel! It’s not as easy to use as it looks, and with that kind of fuzzy documentation it is even harder.

CMake Builder Plugin in Master/Slave Setups

Making the CMake Builder plugin for Hudson behave in master/slave settings.

The first versions of the cmake builder plugin were developed more or less only driven by our own needs. As people began to use it an issue came up that we hadn’t considered yet: distributed builds, a.k.a master/slave mode. So on our first OSLD in 2010 I looked into the plugin and began to rectify the situation.

My test setup consisted of a hudson master on WindowsXP box which was connected via SSH to a slave node in a Ubuntu virtual machine. The first errors were easy to find. The plugin tried to find all configured paths on the windows host and not on the ubuntu slave.

Experience from our previous Crap4J plugin development and a quick read here brought me on the right track. It’s not a good idea to use just java.io.File if you want your plugin to be master/slave capable – use hudson.FilePath instead.

So after replacing all java.io.File occurrences with hudson.FilePath the situation was much better. The plugin handled all paths correctly but still produced errors when calling cmake. I quickly discovered that java.lang.Process and java.lang.ProcessBuilder were used to call “cmake -version”. Again, not a good idea – hudson.Launcher is your friend here.

After replacing Process with Launcher I had only one strange error left. The following launcher call using a nice fluent interface wouldn’t execute on the remote machine but insisted to execute locally.

launcher.launch().cmds(cmakeCall).envs(environmentVars)
   .stdout(listener).pwd(workDir).join();

When I changed it to the seemingly equal statement

launcher.launch(cmakeCall, environmentVars,
    listener.getLogger(), workDir).join();

it worked like a charm.

After all those changes I proudly present the newest version of CMake Builder Plugin which is now ready to be used in distributed environments.

Only one little unpleasantness still exists, though: when configuring the make and install commands the plugin tries to find the executables on the PATH of host machine. For now, you can just ignore the error message. I try to look into it, soon. Apart from that, have fun with the new version.

Readability of Guard Clauses in Methods

A little story about two opinions on readability of methods containing if-clauses.

Browsing through the code base of one of our customers I frequently stumbled over methods that were roughtly structured like this:

void theMethod
{
  if (some_expression)
  {
    // rest of the method body
    // ...
  }
  // no more code here!
}

And most of the time I was tempted to refactor the method using a guard clause, like so:

void theMethod
{
  if (!some_expression)
  {
    return;
  }
  // rest of the method body
  // ...
}

because this is far more readable for me. When I noticed that the methods were written all by the same guy I told him about by refactoring ideas in absolute certainty that he would agree with me. It came as quite a surprise when, in fact, he didn’t agree with me, at all. Even something like this:

void theMethod
{
  if (some_expression)
  {
    // some code
    // ...
    if (another_expression)
    {
      // some more code
      // ...
    }
    // no more code here ..
  }
  // ... and here
}

was in his eyes far more readable than the refactored version with guard clauses. His rational was that guard clauses make it harder for to see the program flow through the method. And a nested if(…) structure like above was very suitable to express slightly more complicated flows.

All my talks about crappy methods and the downsides of highly indented code were not able to change his mind.

I admit that I can somewhat understand his point about the visibility of the program flow through the method.  And sure, the (nested) ifs increase indentation and the number of possible code paths but since there are no elses and no code after the if-blocks, does that really increase the overall complexity?

Well, I still would prefer smaller methods with guard clauses but as you can see, to a great extend readability lies in the eyes of the beholder.

What do you find readable?

Aligning the Abstraction Level with constant booleans

Constant booleans can help to maintain a single level of abstraction in one method. They are less expensive than a separate method and a big improvement over a mere comment.

If you ever have done consulting, mentoring or teaching on programming techniques I’m sure you have experienced joy as well as disappointment when your “students” either took on your advice and followed it in their day-to-day work or when they just did what you said as long as you sat next to them but forgot all about it the next day. The disappointing behavior often comes from them not fully appreciating, or not being able to fully recognize the advantages of your solution. (And as you are the mentor/consultant/teacher, the latter might also be your fault).

One example for that is the principle to operate on only one level of abstraction within a method or function. See here for a detailed explanation. I have been applying this technique more or less unconsciously already for a long time now and was reminded of it as the Single-Level-of-Abstraction-Principle in Robert C. Martin’s Clean Code.

I have been trying to put this principle in peoples minds for some time now but often with little success. Sure, they often do see the advantages of arriving at much more readable code but they often ignore it in their own code. Most of the time they just don’t see the necessity to create another method with a meaningful name or they content themselves just with putting a comment above some chunk of lower abstraction code (The resulting loud screams for a Extract-Method refactoring often remain unheard, too)

Lately, I did have fairly good success with one little sub-technique of this principle: constant booleans for if-statements. That is, instead of (C++ code):

void someMethod()
{
   if (hard_to_read_boolean_expression_using_lower_abstractions)
   {
      // do stuff
   }
}

you write:

void someMethod()
{
   const bool expressive_name = 
      hard_to_read_boolean_expression_using_lower_abstractions;
   if (expressive_name)
   {
      // do stuff
   }
}

I guess the main reason for the success of this sub-technique is that it increases readability a lot at a cost that is only a tiny bit greater than a simple comment.

True, in many cases it may be even more readable to put the whole if-statement in another method, but using a boolean constant like above is already a big improvement.