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.

Exercise

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.

6 comments:

Tyr said...

[] could not return anything, as it is the wrong type. [] cannot be [[Bool]].

The function could be `any and` and would return True for [[]].

Neil Mitchell said...

Tyr: [] is of type [[Bool]] - the outer list is empty, so there are no elements of the inner list. [] :: [a], and [a] can be instantiated to [[Bool]].

I like your concise definition of the function - when I tried this exercise I was just thinking about the corner cases. It turns out the implementation would have been massively simpler to reason with! (With your definition you can easily try what it gives on [])

spyked said...

"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."

I guess the workaround would be putting the method call in a try-catch sequence. Maybe it's not the most elegant solution, but it certainly works best in C#/Java.

Also, it should be noted that Haskell also throws exceptions when using head or tail on an empty list. It's not necessarily a bad thing, only there's no alternative such as safeHead :: [a] -> Maybe a, so you'll have to define that by hand if you need to use it.

Neil Mitchell said...

spyked: Haskell does sometimes throw exceptions in corner cases, but in the case of head/tail there is no sensible value that fits with the semantics of the function. For DrawToBitmap (and new Bitmap(0,0)) there are perfectly sensible semantic interpretations at the corner cases.

I tend to avoid try/catch and try and make my functions robust with parameter checking etc - it's all too easy to try/catch your way round a problem, and find you are accidentally suppressing some real error you didn't expect. You can then put a try/catch at the top level to catch anything that slips through.

rampion said...

`replicate (negate 1)` is a pretty huge corner case. In your implementation, it's equivalent to `repeat`, but in the GHC implementation, it's `const []`. Which is a pretty big difference.

I'm not saying that a clean implementation (with recursion and other fp techniques) doesn't help us design with certain corner cases in mind, just that it's no panacea. There's still a need for testing.

Though, this could be a good use case for a natural number type - as input to `replicate` or `!!`, or output of `length`.

Neil Mitchell said...

rampion: Yes, I realised that replicate had that problem. I considered writing something about natural numbers etc as well, since they'd have been useful for DrawToBitmap too, but decided against it.

I guess the message is there are corner cases (0) which you should handle properly and error cases (-1) which you should throw meaningful errors on.