Here’s another brain dump… I’m working on adding opacity support to QGraphicsItem and possibly QWidget, and have run into a common inside pattern, with a common problem to solve. Figured I’d share it with those interested.

Many of Qt’s properties propagate, some do in different ways, but the general pattern is that you set or modify a property on a widget or an item, and that property has some effect up and/or down its hierarchy. This is a good API pattern. Propagation is most often what you want, and you’re often surprised when a certain property doesn’t propagate (like QWidget::style).

• Q{Graphics,}Widget::visible - if you explicitly show a widget, its implicitly hidden descendants are shown, explicitly hide a widget, and visible children are all implicitly hidden
• Q{Graphics,}Widget::enabled - if you explicitly enable a widget, its implicitly disabled descendants are enabled, explicitly disable a widget, and its enabled descendants are implicitly disabled
• Q{Graphics,}Widget::palette - you set a mask [*] of modified palette entries, the palette is resolved against its ancestors, and propagates to children
• Q{Graphics,}Widget::font - you set a mask of modified font entries, the font (or rather -request) is resolved against the widget’s ancestors, and also propagates to children
• Q{Graphics,}Widget::pos - if you move a widget, its children move with it
• QGraphicsItem::transform - if you transform an item, its children transform

There are plenty of other properties that propagate. How does this actually work on the inside? Let’s take a look at visibility, as an example. QWidget::visible’s setter, QWidget::setVisible() (which is called by show() and hide()), sets local state only, and doesn’t touch other parts of the hierarchy - so the setter is “cheap”. Checking isVisible() is also cheap, but what you get from isVisible() is local state only; determining whether the widget will actually be visible to you when its window is shown, requires some more work. It’s relatively expensive to resolve “true” or “effective” visibility for a widget (compared to the setter anyway). Luckily though, QWidget’s visibility property is cleverly designed so you very seldom need to call show() or hide() at all, and I don’t know of any case where I’ve ever had to check my widget’s “effective” visibility. This is all done inside Qt. And that’s good, since we can do clever stuff to avoid the resolving expense. Because visibility rarely changes, we could even cache it.

For the record, if you want to know your widget’s effective visibility, there’s a handy QWidget::isVisibleTo() [**] that you can use:

if (widget->isVisible()) {
    // Whether this widget's local state is visible. But if the
    // parent is hidden, this widget is also effectively hidden.
}
QWidget *window = widget->window();
if (window->isVisible() && widget->isVisibleTo(window)) {
   // Yup, unless the window is outside your desktop, and unless
   // you've turned off your monitor, or perhaps you don't even
   // have a monitor at all, it should be visible. 
}

OK, so let’s give an example of the opposite, a propagating property with a cheap effective getter and an expensive setter: QWidget::palette. When you set a palette, this palette is first resolved against the parent palette, and then explicitly propagated to all descendants. This operation can be expensive, depending on how deep your descendant hierarchy is. Why is the setter expensive? Because unlike QWidget::visible, which changes quite frequently during the runtime of an application (think how many times you open and close menus, dialogs, switch tabs, show and hide docks, minimize and maximize windows), palettes are very rarely changed at all, and mostly assigned once only, right before the widget is shown for the first time. So every time the widget is drawn and you need to access the palette, it’s very cheap and easy to access.

Expensive assignment, cheap resolve

If you think your property will be assigned only once-ish, and you need it to propagate, you go for the cheap resolve and expensive assignment. Typically this involves storing local state in every single child, so it’s also a memory vs. speed trade-off. This implicitly makes the individual child widget’s resolve step (”effective property resolve”) cheap. Using the example above, when you set a palette with a blue color entry for QPalette::Link, QWidget::setPalette will immediately walk the child tree and resolve all child widgets’ palettes against this new entry. So if the deepest descendant needs to redraw itself (or paint using QWidget::render), it has a fully resolved copy of the palette in its private section.

Laziness can help a lot here; you can speed up the expensive assignment by setting a dirty state on all non-dirty descendants - now the resolve is will only happen on access. The setter is the same order of complexity though, it’s still expensive. There’s still room to be clever :-).

Expensive resolve, cheap assignment

If you think your property will be assigned several times, and relatively rarely used, you go for the cheap assignment and expensive resolve. QWidget::pos, for example. Changing the position of a widget is something you might not do very many times yourself, but you can be sure that the layout system does this very many times for many different widgets in the same form (although only once per widget). Making the setter propagate its state immediately, like QWidget::palette, would mean form resizing would become a quadratic operation (for each widget, set the position and adjust all descendants’ positions). So instead, you set local state only. Now, when the widget is rerendered, Qt walks the tree to calculate each widget’s effective position, but it only needs to do this only once per paint event.

Caching can help here, tremendously in fact. When you resolve the state of a leaf node, you cache all resolved states for its parents all the way up to the ancestor. Now, if you need to resolve another leaf, there’s a fair chance you’ll hit a node that already has a resolved state for you. The complexity is still O(N lg N), but the cut-off makes the common case O(N).

So the question is - which approach to choose for widget opacity?

— Andreas

[*] From the outside, QFont and QPalette look like actual value classes, but a little-known secret is that they actually represent a request set. When you assign a palette or a font to a widget, you’re not actually overriding any other entries than the ones you explicitly set, and even those might be modified to match what’s available. This is why neither QWidget::font nor QWidget::palette have symmetric setters and getters (the getters return the resolved palette).

[**] Qt 3 has QWidget::isVisibleToTLW(), which is obsolete (but present) in Qt 4. This does the same as widget->isVisibleTo(widget->window()) < = which is much clearer and doesn't use ugly abbreviations. :-)