Example of a hierarchical tree model in Qt.

The example uses Qt 5 and libxml2 (via libxxxml) to work on XML trees and libxfsx to work on binary files encoded in the BER ASN.1 flavour. It implements an abstract tree model and provides an adaptor to QAbstractItemModel. In addition to that, a generic Undo/Redo class interfaces with QAbstractItemModel.

An example GUI editor is included to demonstrate the model in action with XML and ASN.1 BER files.

Each class has several unittest test cases. Besides catching errors and regressions, they can also be consulted as examples how the different APIs are intended to be used.

2016, Georg Sauthoff mail@georg.so

Challenges

Build system

CMake is used - cmake usually makes it easy to build C++ projects, but the CMake Qt support is relatively new, is not extensively documented and there are some tutorials available that use deprecated cmake Qt commands.

There are also pitfalls, e.g. if you use namespaces and want to generate Qt moc files for classes with the same name that are located in different namespaces. As of 2015, this yields collisions if you use CMAKE_AUTOMOC ON.

Similar issues occur with .ui files, only worse - even if you omit CMAKE_AUTOUIC, all files are still generated in the top level build directory.

Unittesting

Structuring the code into models, controllers, views; thus separating GUI parts as much as possible from non-GUI functionality also simplifies how to test much of the code. But still, view related parts need to be tested as well - and this is a challenge - because you basically have to automate a GUI.

The example demonstrates with a dialog test-suite (ut_select_open) how to use QTest. In that test-suite, QTest is used to execute the tests, check assertions, inject key press and mouse click events and to spy on signals.

It is perhaps not entirely obvious how to use general purpose unittest libraries for testing Qt GUI elements. The test-suite ut_gui demonstrates it - it uses Catch for execution, assertion etc. and QTest only for event injection and signal spying.

Subclassing QAbstractItemModel

Using QAbstractItemModel for hierarchical models assumes that following operations run fast: 1) determine the number of children of a node 2) Random access the k-th child 3) determine the rank of a node (i.e. the position inside the siblings list).

It seems that these operations are often not implemented in existing hierarchical data structures, because they are not needed for other use cases and implementing them has a cost. In this example, the existing hierarchical data structure is a DOM-like XML node tree generated by libxml2. It does not efficiently support these operations. Thus, inspired by QAbstractItemModel, the abstract model class tree_model::Base is created that does not require these operations. The class tree_model::Item_Adaptor is derived from QAbstractItemModel and maps its calls to tree_model::Base ones. It does so via caching and using ranked lists, a data structure where random access are efficient.

Rank Operations

As part of the tree_model::Item_Adaptor a data structure is needed that allows for efficient rank operations (e.g. accessing the k-th element or determing the rank of an element). Just using a combination of lookup tables and a list is not sufficient, because operations like removal and insertion should be effiecient as well. A ranked list is a skip list variant (cf. list/ranked_list.hh for details), i.e. it is a probabilistic data structure.

Undo/Redo

Qt does not provide an API for implementing undo/redo operations on QAbstractItemModel models. In general there are two approaches to undo/redo: 1) make your data-structure immutable (like in functional programming, thus you get old versions of it 'for free' 2) create an edit operation object that contains enough information to reverse it,for each change, and put those objects in a list.

The first approach is only an option if you design your tree data structure from scratch. In case the undo should be limited (to safe space) the removal of old elements might be challenging.

The second approach arguably is simpler but does not really scale if many different kind of edit operations need to be covered. But this is not the case for an QAbstractItemModel model, where you need to cover 'just' set-data, insert and remove.

Thus, the tree-model library implements the 2nd approach for undo/redo in the class tree_model::Recorder. An Recorder instance is associated to a QAbstractItemModel instance via being connected to all its 'interesting' edit related signals. It records edit operations via storing edit operation objects into double-ended queue. Transactions and limited undo are supported, where unlimited undo/redo is the default.

Clipboard Support

Qt has a class for interacting with the system's clipboard in a portable fashion. When dealing with QAbstractItemModels it is natural to also use the drag-and-drop related methods dropMimeData() and mimeData() to paste and copy the clipboard data. The adaptor model thus also implements them and translates them into equivalent calls of the tree_model::Base model.

Using XML as the serialization format of the clipboard has the advantage that it is human readable and can be easiliy changed with a normal text editor. When multiple elements should be copied or inserted one has to decide how to map that to XML since an XML document may only have one root. One possibility is to create an artificial root element that is part of the mime data. The editor example implements a variation. The serialized XML is just a concatenation of serialized subtrees, thus, not necessarily a valid XML document as such. But, on deserialization the document is implicitly wrapped with an artificical root element such that an off-the-shelf XML parser can be used (after insert that root is discarded).

With the Qt clipboard API one has to decide which clipboards to support exactly. For example under X11, there is the primary selection buffer and a normal clipboard. Also, a clipboard may contain a document in several versions (with different mime types). The editor example thus exports a copied selection multiple times: into the selection buffer, into the normal clipboard as normal text and with mime-type 'text/xml'. The normal text copy is done because this is what normal text editor request; such that the 'text/xml' version is ignored. The mime-type 'text/xml' is what is expected by the editor - also for drag-and-drop operations. The X11 selection copy is done for convenience, e.g. to easily paste something into a terminal window.

Drag and Drop

After central methods of the QAbstractItemModel are implemented in the tree_model::Base (like removal, mime data export/import) it isn't much work to get drag and drop functionality enabled in the view and the model.

See also

• Item_Adaptor::mimeTypes()
• Item_Adaptor::mimeData()
• Item_Adaptor::dropMimeData()
• Item_Adaptor::canDropMimeData()
• Item_Adaptor::supportedDropActions()
• Item_Adaptor::flags()

and

• XML::mime_types()
• XML::mime_data()
• XML::drop_mime_data()
• XML::can_drop_mime_data()
• XML::supported_drop_actions()
• XML::flags()

and the Tree_View constructor for details what is necessary to implement and customize drag-and-drop (supporting copy and move actions) for hierarchical models.

UI

Creating dialog and widgets, thus, distributing the widgets and configuring layout policies can get challenging. Thus, a graphical editor like the UI component of Qt-Creator is a help. Challenges still occur, e.g. if you want to use namespaces. It is possible, but the support in Qt Creator is limited (as of 2015).

File Open Preview

Everybody likes file previews in file open dialogs. Unfortunately, the Qt File Dialog doesn't provide an API for adding preview widgets. Thus, one has two alternatives: either implement a file open dialog with preview from scratch or modify the existing one.

The class editor::Preview_Dialog is an example how the existing QFileDialog can be extended to include a preview widget. For that, it accesses the internals of the dialog, i.e. it gets and modifies the geometry manager of the file dialog.

It also deals with one pitfall with that approach: depending on the platform, Qt uses the native file dialog by default. Thus, the extended dialog changes that default such that a modifiable Qt file dialog is used.

Multiple Windows

The editor supports multiple windows, i.e. for editing multiple files side by side or opening subtrees in extra windows.

The 'challenges' arise from having to manage the different open files. The editor thus implements a editor::Instance_Manager that creates and 'manages' instances of MVC tuples. For example, it quits the application in an orderly fashion - i.e. when multiple windows have unsaved changes the user is given the opportunity to save them.

Blocking UI

The human eye is very good in noticing visual glitches - and a UI that blocks - even only for short amounts of time - is one of them. Blocking the UI results from functions running long enough in the main thread (i.e. the GUI thread) such that UI relevant events queue up to wait to be processed.

There are basically two approaches to deal with that:

1. Starting a worker thread for the long running function such that the GUI thread can execute its event loop without hindrance. When the worker thread is finished the GUI is notified via a thread safe (i.e. queued) connection. The open and save commands (cf. editor/command/async_{open,save}* and editor/gui_command/{open,save}*) are examples for that.
2. Calling a process-events function from time to time in the long running function thus such the work is interleaved with GUI event processing. See also editor::gui_command::Write_ACI for an example.

Multi threading may introduce the usual complications. For example, the long running function may work on the model that is also used by the view and is not thread safe, in general. Or, a cancellation of the long running function, triggered by a user action, must be delivered to the other thread.

Besides that, the QThread class can be used in two modes:

1. Extending it and overwriting its run method (which is executed in the new thread). The thread doesn't have an event loop then.
2. Using the default QThread::run() method that starts an event loop (it calls exec() and move the worker object with the long running function to that thread.

QObjects have the concept of thread affinity. By default an object is affine to the thread where it was created. But it can be moved to another thread. Unless it has a parent. Also, the move-to operation must be executed by the current affine thread.

The thread affinity implicates a few things:

1. The object must be destroyed in the thread where it is affine to. This can be easily achieved via connecting deleteLater.
2. Signals that are emitted in a thread that is not affine to the receiving object are queued by default (cf. queued connection). They are thus thread safe.
3. The QThread object itself is affine to the creating thread. Thus, any connection where it is involved in are direct connections. That means that QThread slots are also executed in the creating thread.

Some pitfalls with QThread:

• a QThread must not be deleted when its event loop is still running because the destructor doesn't gracefully shutdown the event loop. It is only save to delete a QThread that is finished. Thus, in most cases, it is not advisable to create a QThread with the parent attribute set.
• same goes for a QThread with a custom run method (i.e. without event loop) - it is finished when it has returned from the run() method
• Objects directly created in the overwritten run() method must not use this as parent because then the parent has a different thread affinity than the child - which is not allowed. (The QThread object itself is affine to the creating thread where the objects created in run() are affine to the newly created thread, i.e. the thread that is 'represented' and wrapped by the QThread object.
• Objects created in the (overwritten) constructor of a QThread (extended) class are affine to the creating thread.

The editor only moves objects to QThread objects. It doesn't extend QThread.

Interleaving the work function with processing GUI events (the approach) is an alternative to multi-threading but adds some complexities on its own. For one, existing worker functions usually don't provide callbacks where control can be yielded to event processing. Also, the process-events function shouldn't be called to often (too much overhead) - but if it is not called often enough than the UI is blocking again.

Delegate Editing

Data returned from the model is wrapped in a QVariant. Thus, it can be returned as one of several types that is supported by QVariant. Since data requests contain a role argument, one can return different types (and different content) depending on - say

• whether the data is needed for display or edit purposes.

When a value is accessed for editing, different types yield different edit widgets. For example, a QString is by default edited inside a QLineEdit, where a QDateTime value is edited inside a QDateTimeEdit widget. Which type is edited by what editor is configured in an editor factory class. A default factory class is set up, but it can be replaced with user defined one (cf. QItemEditorFactory, QStandardItemEditorCreate{Base,}).

By default, QVariant only supports some of Qt's types. But, user defined types can be made known to it, as well - via Qt's meta type system (cf. Q_DECLARE_METATYPE and QMetaType). Since Qt 5.2, the meta type system also supports registering comparison and conversion function for user defined types. See for example editor/delegate/value/local_time.cc for a type where a string conversion member function is registered. With that QVariant::toString() works as expected (useful e.g. when existing code assumes string convertibility).

For widgets that use QAbstractItemModels, Qt provides another orthogonal mechanism: item delegates (cf. Q{Abstract,Item,Styled}ItemDelegate). Each model using widget has a default delegate that can be replaced with a user defined one. Such delegates can also be set for certain columns (cf. QTreeView).

The motivation for customizing the editing of model data is that there are domain specific requirements such as validation of edited data (cf. QValidator) and completion during editing (cf. QCompleter). Also, specialized widgets like a calendar popup can simplify the editing process.

The editor application contains examples for both delegating mechanism - see for example editor/delegate/tag.* for an delegate class that installs a domain specific completer and validator on certain widgets. Under editor/delegate there are also classes that declare custom types to the meta type system and register editor widgets.

Whether to use the meta type system and register an editor at the factory or install explicit delegates on a widgets depends on the use case. For example, the state that is needed for creating the editor widget must fit into the value class when an editor factory should be used. A - say - small context dependent database for completing strings thus makes an explicit delegate class necessary.

Searching

The editor implements fast searching while maintaining a responsive GUI via directly traversing the tree data structure in a worker thread (cf. editor/command/{async_,}search.cc and editor/gui_command/search.cc).

It is tempting to use the libxml2 XPath module for searching the tree. Unfortunately, even a simple XPath expression like //Imsi[. = '123'] yields very huge temporary nodesets. Thus, it is unusable for large documents (think thousands of nodes, think 100 MiB BER files). Apparently, the library doesn't optimize the expression much (e.g. lifting the test).

For smaller documents, not using XPath also improves on constant factors, of course.

Using a worker thread, a few synchronisation implications lead to following implementation choices:

• the abortion of an ongoing search is signaled via an atomic integer
• the transfer of the result list from to the worker to the GUI thread is done via std::move() and is protected with a mutex
• during the search the adaptor model is switched read-only to avoid invalidating the traverser
• the search directly traverses the tree data structure for performance reasons (i.e. elimination of temporary QModelIndex and QVariant objects), but also because the adaptor model maintains some data structures for caching that are not thread safe

Architecture

Qt provides some classes to implement data models and views. This is similar to the MVC architecture - but without the separation of the controller. Thus, the Qt documentation consequently calls its variation just model/view architecture and argues that combining the view and the controller would simplify the framework. This might be the case - but it also doesn't help with simplifying the structure of the application.

Thus, the challenge in writing a graphical Qt application is to decide where to put the non-view/non-model logic, i.e. the controller logic. The code that fills and changes the model, executes actions in response to a clicked button etc.

Scatter such code around some view parts doesn't seem to be a good idea. Especially since the result isn't testable, hard to maintain and not reusable.

The graphical example application separates view code from controller code as much as possible. Dialog and widget classes don't contain any controlling code. Instead, they expose signal and slots that are connected by a controller class to command objects. The controller and the command classes are separated into a non-GUI and GUI part, where the GUI part extends the non-GUI one. For example, the open command reads a file and creates the model - the GUI part extends that command and adds a graphical progress dialog to it.

Structure

Repository Overview:

tree_model/          Tree model, QAbstractItemModel adaptor,
                     undo/redo recorder etc.
   operation/        Operations supported by the undo/redo
                     recorder
list/                Ranked list datastructure used by the
                     tree model adaptor
libxxxml/            Thin libxml2 C++ wrapper, git submodule
editor/              example GUI application using the tree
                     model, i.e. an XML editor.
                     Directory contains widgets, dialogs
                     and application specific classes (e.g.
                     argument parsing).
    command/         Commands that can be used without a GUI
    gui_command/     Commands that need a GUI, e.g. because
                     they display dialogs.
    controller.*     Owns the command objects and the model.
                     Connects them together.
    gui_controller.* Graphical part of the controller
    main.cc          Defintion of the editor's main()
                     function.
test/                Unittests, subdirectories mirror the
                     repository structure.
    main.cc          Setup of [Catch][catch] based non-GUI
                     testsuite.
    gui_main.cc      Setup of [Catch][catch] based GUI
                     testsuite.
    test.cc          Setup of [QTest][qtest] based GUI
                     testsuite.

Tree-Model classes:

Base               Tree-model base class
                   no random access methods
Index              References a node inside Base
XML                Implements the Base tree model for a libxml2 DOM-like
                   tree data structure
Item_Adaptor       Translates between an associated Base
                   tree model and a QAbstractItemModel
Deep_Model_Index   Converts a QModelIndex into a persistent
                   reference
Recorder           Records edit operations of an associated
                   QAbstractItemModel and provide undo/redo.

License

LGPLv3+