2009-11-26

Multiple Inheritance and the Dreaded Diamond

Woopsi refactoring continues apace. Today’s latest changes were an attempt to consolidate the ListBox, ContextMenu and CycleButton gadgets.

Each of these gadgets is a different kind of view onto a list of items. The ContextMenu is the most primitive - it shows all of the items in its list as a vertical list. The ListBox is basically the same thing, except it introduces scrolling into the mix. The CycleButton shows just one option at a time; the other options can be paged through by clicking the button.

At present, the ListBox has the most advanced data mechanism. It leaves all of the data functionality to the ListData class, which wraps around a WoopsiArray (ie. vector) and provides such handy functions as sorting and item selection/deselection (enforcing single-only or multiple selection rules). It raises events to indicate changes to the data or selections within the data.

Meanwhile, the CycleButton and ContextMenu classes have very primitive data manipulation functionality. They both include an instance of the WoopsiArray and work with it directly. Wouldn’t it be better if they could benefit from the wealth of functionality in the ListData class?

Since the ContextMenu and ListBox work in very similar ways - the ContextMenu is basically a customised ListBox without scrolling - it makes sense to create a base class providing the most basic list view functionality that they can both inherit from. I split up the ListBox into “BasicListBox” (no scrolling) and “ListBox” (inherits from BasicListBox and ScrollingPanel, which adds the scrolling functionality). Here the problems began.

The BasicListBox inherits from the fundamental Gadget class, from which all Woopsi UI components inherit. The ScrollingPanel also inherits from the Gadget class. When the ListBox attempts to inherit from them both, it ends up with two copies of the Gadget class floating around in its inheritance hierarchy. Any attempts at working with the features of the Gadget class are now ambiguous and the compiler throws errors all over the place. This is called a “diamond” inheritance pattern:

           Gadget
       /             \
      /               \
     /                 \
BasicListBox    ScrollingPanel
     \                 /
      \               /
       \            /
           ListBox

The C++ FAQ Lite has a whole page about the diamond inheritance problem. The solution is to declare the inheritance from Gadget as virtual, which eliminates the ambiguities by eliminating the second copy of Gadget. However, attempting to do this has horrible problems in the Woopsi codebase. C-style casting cannot be used (uh oh) and the class at the top of the diamond (in this case, Gadget) should not include data members that need to be initialised (it can, but it shouldn’t).

The upshot of all this is that it is impossible to create a gadget that inherits from two other gadgets in Woopsi. If you think about it, this does make sense. It doesn’t help my goal of rationalising the list display gadgets, though. I could include an instance of the ScrollingPanel inside the ListBox to achieve the same effect, but that would be less efficient than the current solution. I could alternatively make the ListBox the basic list and have the ContextMenu inherit from that, and just not use the scrolling feature (though it would be handy if there are too many items to fit on-screen at once), but again that’s less efficient than the current solution.

I kept some of the changes I made before I reverted everything else back. ListData::swapItems() no longer raises a data changed event, as the only place it is called is in the sort() method. That method now raises the event instead. The ListDataItem struct has been replaced with a ListDataItem class, and it includes a C#/Java-style compareTo() method. Subclassing the ListDataItem and overriding this method allows the ListData class’ sort() method to sort the list differently. The ListBox’s scrolling canvas now has the correct height and the extra 1px at the bottom of every ListBox has now gone.

Finally, there are a couple of fixes in other places. The Woopsi class’ constructor no longer tries to retrieve the system font before it has been initialised, and the ContextMenu does not cast away the const-ness of the ContextMenuItem when raising a selection event to its listeners.

Comments

Richard Quirk on 2009-11-27 at 08:26 said:

Java-style interface inheritance may be one way to go. You tend to get into the diamond pattern problem when you use inheritance to gain functionality (actual code) rather than for fulfilling a contract. If you went this way, Listbox would inherit from gadget and “some interface”, and delegate off the calls to member scrollingpane and basiclistbox variables. Figuring out what “some interface” is becomes the challenge.

The other way is to use something like the decorator pattern, but essentially it all boils down to the same deal: interfaces (or classes that only have pure virtual methods, in C++ speak). Meh. Accidental complexity sucks.

Ant on 2009-11-28 at 17:07 said:

Yeah, now that I’ve seen this problem I have a greater appreciation for Java and C#’s decision to go for single inheritance and interfaces over multiple inheritance. I’d guess that the diamond problem is one of the primary reasons for this.

I’ve looked for an explanation for why these two languages opted for single inheritance. Java and C# coders justify the lack of multiple inheritance by mumbling about it being “hard”, but don’t give anything more concrete than that. C++ coders mock their bytecode brethren by pointing out that multiple inheritance really isn’t that hard at all, and that their tinpot virtualised languages just aren’t powerful enough to deal with it. It’s only when you encounter this particular problem that it starts to make sense - unless you are aware of the diamond problem from the start and either design your program to cater for the situation or avoid it entirely, multiple inheritance can be a pain in the behind.

I pondered the problem in Woopsi for a while and eventually decided that the most appropriate way to achieve this is to have a ContextMenu class that contains a ListBox object. The ContextMenu uses the ListBox, but it isn’t a ListBox. The whole diamond problem was really a case of wrong-thinking about the situation.

Chase-san on 2009-11-30 at 23:04 said:

Aye, some things in C++ are great others things I miss from ‘simpler’ languages (such as anonymous functions).

This is off topic, but how did you, if you did,go about making it render on demand for the dual screen 3D system (so the top screen will render more if needed or the bottom). I am currently struggling with this problem. Since there are times when I need to draw many things on screen and it slows down the overall rendering when they are there. If no screen needs updated neither are.

If there is another option I am all ears (perhaps there is a form of retained rendering mode I do not know about). However ~160 quads didn’t seem that complicated. :)

Ant on 2009-11-30 at 23:39 said:

Woopsi doesn’t use the 3D system. It uses 2D mode 5 on both screens - two 16-bit backgrounds. You can see the setup code in the initWoopsiGfx() function in woopsifuncs.cpp.

It uses all sorts of tricks to make rendering faster. First of all, when possible, it uses the DMA to simply copy chunks of VRAM around. Whenever Woopsi draws a filled rectangle (which is most of the work a GUI does, visually), horizontal line, filled circle, filled ellipse or a bitmap to the display, it uses the DMA to just copy existing memory around as quickly as posslble.

Secondly, it doesn’t do any double-buffering. It works directly with a single background bitmap for each display. That means only one set of write operations is ever performed for each graphical operation.

Thirdly, the display is entirely canonical - what you see on the display is the current situation within the GUI. Windows XP and similar interfaces have two phases - an “interaction” phase and a “refresh” phase (as I understand it). In the interaction phase, all user interaction is received and handled. Any areas of the screen that are invalidated during this phase (due to pending updates) are stored as a collection of dirty rectangles. In the second phase, the refresh, the collection of dirty rectangles is redrawn. Thus, what you see isn’t necessarily the real situation if the UI is part-way through a cycle. Woopsi performs all display updates immediately, which is essential for the DMA optimisation in point one.

Fourthly, whereas modern windowing systems (OSX, Windows 7, maybe Compiz) store all of the windows separately in graphics memory and create a composite for onscreen display, Woopsi has its single canonical bitmap per frame. It wastes no time re-compositing the display when anything changes; it just updates the changes as they occur.

Not sure if that answers your question or not!

Chase-san on 2009-12-01 at 21:19 said:

Nope! But thanks.