Sunday, February 13, 2011

Corner Cases And Zero (and how WinForms gets it wrong)

Summary: Zero is a perfectly good number and functions should deal with it sensibly. In WinForms, both the Bitmap object and the DrawToBitmap function fail on zero, which is wrong. Functional programming (and recursion) make it harder to get the corner cases wrong.

Lots of programming is about reusing existing functions/objects. Many types have natural corner cases, e.g. an empty string, the number zero, and an array with zero elements. If the functions you reuse don't deal sensibly with corner cases your functions are likely to contain bugs, or be more verbose in working around other peoples bugs.

C#/WinForms has bugs with zero

Let's write a function in C#/WinForms which given a Control (something that can be displayed) produces a Bitmap of how it will be drawn:

public Bitmap Draw(Control c)
Bitmap bmp = new Bitmap(c.Width, c.Height);
c.DrawToBitmap(bmp, new Rectangle(0, 0, c.Width, c.Height));
return bmp;

Our function Draw makes use of the existing WinForms function DrawToBitmap:

void Control.DrawToBitmap(Bitmap bitmap, Rectangle bounds)

The function DrawToBitmap draws the control into bitmap at the position specified by bounds. This function is useful, but impure (it mutates the bitmap argument), and somewhat fiddly (bounds have to satisfy various invariants with respect to the bitmap and the control). Our Draw function only handles the common case where you want the entire bitmap, but is pure and simpler. (Our Draw function can be renamed DrawToBitmap and added as an extension method of Control, making it quite convenient to use.)

Unfortunately our Draw function has a bug, due to the incorrect handling of zero in the functions we rely on. Let's consider a control with width 0, and height 10. First we crash with the exception "Parameter is not valid." when executing:

new Bitmap(0, 10);

Unfortunately the .NET Bitmap type doesn't allow bitmaps which don't contain any pixels. This limitation probably comes from the CreateBitmap Win32 API function, which doesn't allow empty bitmaps. The result is that our function cannot return a 0x10 bitmap, meaning that lots of nice properties (e.g. the resulting bitmap will be the same size as the control) are necessarily violated. We can patch around the limitations of Bitmap by writing:

Bitmap bmp = new Bitmap(Math.Max(1, c.Width), Math.Max(1, c.Height));

This change is horrid, but it's the best we can do within the limitations of the .NET Bitmap type. We run again and now get the exception "targetbounds" when executing:

c.DrawToBitmap(bmp, new Rectangle(0, 0, 0, 10));

Unfortunately DrawToBitmap throws an exception when either the width or height of the bounds is zero. We have to add another workaround to avoid calling DrawToBitmap in these cases (or at this stage perhaps just add an if at the top which returns early if either dimension is 0). The Bitmap limitation is annoying but somewhat understandable - it is driven by legacy code. However, DrawToBitmap could easily have been modified to accept 0 width or height and simply avoid doing anything, which would be the only sensible behaviour at this corner case.

The problem with bugs in corner cases is that they propagate. Bitmap has a limitation, so everything which uses Bitmap inherits this limitation. The DrawToControl function has a bug, so everything built on top of it has a bug (or needs to include a workaround). The documentation for Bitmap and DrawToControl doesn't mention that they fail at corner cases, which is unfortunate.

Induction for Corner Cases

One of the advantages of functional programming is that defining functions recursively forces you to consider corner cases. Consider the Haskell function replicate, which takes a number and a value, and repeats the value that number of times. To define the function it is natural to use recursion over the number. This scheme leads to the definition:

replicate 0 x = []
replicate n x = x : replicate (n-1) x

The function replicate 0 'x' returns []. To get the corner case wrong would have required additional effort. As a result, most Haskell functions work the way you would expect in corner cases - and consequently functions built from them also work sensibly in corner cases. When programming in Haskell my code is less likely to fail in corner cases, and more likely to work first time.


As a final thought exercise, consider the following function:

orAnd :: [[Bool]] -> Bool

Where orAnd [[a,b],[c,d]] returns True if either both a and b are True, or if both c and d are True. What should [] return? What should [[]] return? If you write this function recursively (or on top of other recursive functions such as or/and) there will be a natural answer. Writing the function imperatively makes it hard to ensure the corner cases are correct.