Welcome back for the third installment in my series (see Part 1, Part 2) wherein I chronicle my efforts refactoring some code I wrote over four years ago to implement a chess rules engine and WinForms control using C# under .NET v1.1.  I’m hoping to demonstrate over the next few posts a few tips, techniques and tricks to improve established code with refactorings, unit tests and application of best practices that you might find useful in your own endeavours.

Last week I mentioned two tools that I’ll be using from this point forward to support constructing and running unit tests so we can backstop our new code against making destructive changes that would otherwise bust the build or introduce new bugs that we didn’t intend:  NUnit and TestDriven.NET.  For the impatient out there, we will be getting into refactoring soon, but as we’ll see below, I ran into a little issue as a result of setting up my tests that necessitated some backtracking.

Briefly, here’s a quick overview of each tool:

In spite of rumours on its demise, NUnit is very much the de facto if not the de jure free (as in beer) unit test suite for the .NET Framework.  Yes, Visual Studio 2005 in the Team Editions supports its own unit test framework, which looks a lot like NUnit tests with differently-named method and class decorators, but I prefer the original.  NUnit is modeled after JUnit, the Java unit test suite which in turn was based on seedwork by Kent Beck in Smalltalk – it has, therefore, a pretty solid pedigree.

NUnit provides you with a framework for writing regression test assertions to validate code behaviours along with both a console and GUI test runner harness.  If you haven’t done any Test Driven Development (TDD) before, this will be a pleasant experience as you won’t have to roll-your-own test harnesses to see if your code works – you’ll just run the test assemblies and get immediate feedback on whether they passed or failed.

Another upshot to using a framework like NUnit is the option of later “hooking” your tests into a continuous integration suite like CruiseControl.NET which can synthesize your code versioning, build and tests to run automatically on code check-ins or other triggering events.

I’ve installed the latest stable version of NUnit for this exercise: 2.4.3 for .NET 2.0.

While NUnit is the cat’s pajamas for unit testing, and does support some IDE integration, it lacks a certain panache since its test-running goodness is run via an external app.  This can be a throw-the-hands-in-the-air point for some folks who just cannot live without doing everything in Visual Studio, and will forever despise writing and running unit tests without some IDE support.  So, to kick things up a notch and keep these folks interested, on-board and insanely productive, I recommend downloading and installing the TestDriven.NET Visual Studio add-in. 

I won’t go much further into the addin except to say that it allows you the ability to run your tests simply by right-clicking inside either the test fixture class or test method – easy peasy.  If you want to know more, check out the developer’s site for excellent overviews and tutorials.  Ok, here’s a quick screen cap, just to whet the appetite:

I’m using the latest stable version: 2.8.2130 – It runs in all versions of Visual Studio except the Express Editions, which is for a whole host of reasons.

Getting ready to test:  Adding a test fixture project

Once NUnit is installed, all of its core libraries are available to all and sundry projects through the GAC, so all we need to do is create a new library for housing our test classes (aka Test Fixtures) and add a reference to the NUnit.Framework to get access to the all the unit testing goodness.  There are a number of schools of thought on how tests could/should be organized and named – below is my preference:

In this way, I create an NUnit test assembly for each assembly or executable I’m testing and it is clearly identified with the .Tests suffix.  Now, I’ll add references for the RNChessRulesEngine and RNChessBoardCommonTypes projects, since there are dependencies between them;  next, I’ll add a reference to the nunit.framework assembly via the .NET tab in the Add Reference window.  Finally, I’ll rename the stubbed-out class ChessRulesEngine.TestFixture.cs, add some namespace references and an  NUnit TestFixture attribute to indicate that this class will be used for containing test code:

Now that I’m this far, I’ll do a quick build and commit the new project to source control before proceeding.

Supporting the rules engine with preliminary unit tests 

In the last installment, I decided to start my refactoring within the DoPlayerMove(int32,int32) method in the rules engine as it had not only a high cyclomatic complexity score, but was also an obvious entry point for running subsequent routines.  This brings up an some questions:  How do we know if the engine is running correctly right now?  Subsequently, what kind of tests should we be writing?

Note:  If you’ve never written a unit test before, don’t panic:  It’s dead easy.  Check out the NUnit Quickstart tutorial for some examples.

At a fundamental level, we want to craft tests that will demonstrate that the basic operations of the engine are sound, ie. that we trap for bad input, process moves correctly and can play out a game to mate.  My first inclination is to code up a test that would play a well-known, classic game like Capablanca vs. Alekhine 1927 – French Exchange.  This way, I know for certain what the outcomes after each move should be, the material captured, number of half moves (white) and full moves (black) that have occurred, check states for either side’s king and checkmate state.

Algebra rears its ugly head.  Well, sort of.

Sounds like we have a plan, right?  Of course, there’s always a little trip-up:  DoPlayerMove() is a private method that is called by another private method, CommitPlayerMove(), which in turn is called by the publicly-accessible MakeMove().  We have our work cut out for us:  In order to run a sample game through the engine, we need to validate the behaviours for MakeMove() which takes input from two strings representing the Standard Algebraic Notation (SAN) for the “from” and “to” squares, using the numbers 1–8 and letters A-H to represent the ranks and files (rows and columns of squares)respectively.  Thus, if we want to make a basic Queen’s pawn opening, we’d want to move from “D2” to “D4”. 

Let’s build-out a test to verify that the input “D2” and “D4” results in a valid move.  First, we need to add a member object for the rules engine so we can test it, and a special NUnit method to instantiate the object when the battery of tests are run for the first time called TFSetUp():

Note the [TestFixtureSetUp] attribute that tells the NUnit framework to run this method exactly once for every run of our test fixture class.  Next, let’s add a method to exercise MakeMove() with the SAN I mentioned above:

A few things to note here: 

1. The [Test] attribute, which indicates that this method is a unit test and should be executed by the NUnit framework;
2. The test method name follows a convention to make it easy to identify (hat tip to Roy Osherove) the method, test state and expected outcome for the test. 
3. I’m using a classic NUnit assertion, Assert.AreEqual(), which compares an expected value (MoveResult.Legal enum) against the actual value returned from the PlayerMoveStatus property, which is a struct defined in RNChessDataTypes.cs.  I’ve also added a descriptive message that will be returned when the test fails so that we can get meaningful feedback.

Observant keener types will notice that in my Assertion, I’m expecting MoveResult.ILLEGAL.  This is because I want the test to fail first – this way I can be assured that the method is running correctly.  Right-click inside the test method and select Run Test(s) from the context menu – you’ll see the following in the Output pane:

Blammo!  We have our first validation point that the engine is working correctly – it’s taking input for a valid move and is returning a confirmation.  Moving on, we adjust the method to check for PlayerMoveResult.LEGAL and the we get a pass:

Let’s add another test to check out an illegal opening move – say the King’s pawn, three squares forward.  We’ll follow the same pattern as above:

And the same drill as before:  Run the test, watch it fail, then adjust to assert on MoveResult.ILLEGAL; run the test and it should pass easily.

Note that I’ve re-instantiated ChessRulesEngine on line 41 – I wanted to revert the object to its default state so that I could properly test the opening move.  However, why not use the object’s ResetBoard() or UndoLastMove() methods to do the same thing?  Because we want to make sure that our tests can be run in isolation of each other and test only the operations we’re controlling.  By calling in ResetBoard() or UndoLastMove() inside a test method, we’re assuming that they work properly – until we know otherwise, we need to do like Fox Mulder and trust no-one!

So, I need to refactor my test code.  I want to reset the state of the ChessRulesEngine object before each test without having to new one up.  We can do this via a method decorated with the SetUp attribute: 

We can take out line 41 in the MakeMove_OpenE2E5_Illegal() test method, build and run the tests for sanity and revel in our Homer Simpson-style productivity gains.  Don’t forget, we’re starting off easy here – this will pay dividends later on.

Defining What to Test

So far, it seems like we’re being somewhat arbitrary in our tests – while testing this input is good, and we do have a goal for writing a test to run through a sample game, we should have a few “rigor rules” to guide our efforts to make sure we’re writing valuable tests and not just ad hoc queries to satisfy curiosity.  This is where I like to refer to advice from Andy Hunt and Dave Thomas, the original Pragmatic Programmers.

In their book, Pragmatic Unit Testing in C# with NUnit, 2nd Ed., Hunt and Thomas wrap up their experiences for writing top-notch unit tests with three acronyms:

• Good tests are A-TRIP: Automatic, Thorough, Repeatable, Independent and Professional
• Write tests using your RIGHT-BICEP
• Ensure that boundary conditions are CORRECT

I won’t rehash the acronyms here (you can check out the link above), however, suffice to say that we need to write tests that focus on one thing at a time, can be run independent of one another (ie, they don’t require prior tests to be run first) and exercise the code’s extremities, ie. anything that might break and anything that does break.

Let’s Try Breaking MakeMove()

To round out this post, let’s try writing a test to push in bad input to the MakeMove() method to see what happens.  I have no idea what to expect, so I decide to try this:

Running the test, I got the following results:

A-ha!  Now we have grounds for a new assertion – the engine does appear to validate input, throwing an ArgumentException if things are out of whack.  We can test for expected exceptions by adding the ExpectedException attribute to our test definition:

I’ve dispensed with writing this test to fail-first with a different exception, since my initial run provided me with the expected exception.  An important thing to note here is that I’m not writing the tests to pass, but using my knowledge of the system and code as I go to validate assumptions – which can change later on, depending on refactorings.

Next:  More tests, web-accessible source

For the next installment, I’ll be getting into more meaty tests to validate inputs using Hunt & Thomas’ unit test guidelines and  I’m also going to look into setting up web access for the source tree to provide the latest versions of the code via Subversion as we go along.  As part of this effort, I’ll be writing some tests that I’ll share to validate the moves in a historical game.  Until then, as always I welcome input on the posts so far and any constructive criticisms.  Cheers!

In my last entry, I outlined my ambitions for revisiting the code for my .NET 1.1 WinForms chess board control - specifically the rules engine.  This component is responsible for analyzing each move made on the chess board control against the known rules of the game for:

• Legality - Is the piece being moved from/to legitimate squares on the board according to the type?  Is the move blocked?
• Material Captures - Does the move result in material capture?  This includes special capture moves such as en passant, which incidentally has a known bug.
• Check - Does the move result in either placing the player's or the opponent's king under direct attack?
• Check-mate - Does the move result in placing the player's or the opponent's king under attack that cannot be evaded?

There are also some additional methods in the engine that should probably be extracted, since they do not directly relate to the class’ core responsibilities, ie. Standard Algebraic Notation and FEN notations for recording moves and bit-board initialization and manipulation routines.

By the way, don't worry if you're not a chess fanatic or chess programming whiz - I certainly wasn't when I tackled the project!  You should still be able to grok what’s going on – let me know if I’m glossing over material. 

Before we get much further, you might want to pull down a copy of the original source code so you can follow along.  Download it here.  Opening the solution in Visual Studio, here’s where you’ll find the rules engine artifacts:

One thing to note here is the green orbs beside each element in the view – these are Subversion source control status flags that are provisioned via the Visual SVN plug-in for Visual Studio.  Since we’re going to be ripping into the code, it is an absolute must that we use some form of code versioning.  Subversion is free (as in beer), and is professional-grade, with features that I feel rival TFS.  It has a small footprint and can be set up easily on a local box, web server or network share.  In sum, it’s a great all-round tool for managing your code – I’ll do a posting on getting started with Subversion for .NET development in the near future for the curious. 

The class file that contains the rules code I’ll be refactoring is contained in ChessRulesEngine.cs, a rollicking roller coaster of code over 1400+ lines deep (excluding comments) with 121 methods, 164 fields and eight types!  Almost all of it necessary – I think.  Well, except for the 24 #regions – which we all now know are completely evil (right, Bil?).

First thing we do:  Kill All The #regions

I know that I promised to get into my strategies for tackling the high cyclomatic complexity, but before we can get to any refactoring, we need a clean surface.  Looking at this old code, I cringe because it’s a little messy, and I want to make it more in-line with my current habits.

So I began by first removing all the #region statements so that I could see the code I was dealing with without having to mess around with little “+” swizzles and to reveal all the code in its naked glory.  However, I did want to retain some markers about what each block of methods represented, so I did some global S&R to change all “#regions” to “// GROUP:” and “#endregions” to “// — GROUP END —”  I then added GROUP as a task list macro (Tools—>Options—>Environment—>Task List) so that I could easily view and navigate to each section within the IDE:

Now, I could easily move around to each code grouping using descriptive markers.  At this point, I committed my changes to the repository to serve as my new baseline.  As an aside, when using any modern CVS, it is generally a good practice to provide a brief message about the changes you’re committing – getting into this habit will make your life a lot easier should you ever have to revert to a specific revision later on:

Next:  In-depth code analysis

In my earlier post I mentioned two motivations that would provide an initial guide to establishing my refactoring plan:  Maintainability and Cyclomatic Complexity.  Each is complimentary in a yin/yang sense – by tackling methods and types with high CC scores, I would be making strides toward improving maintainability, and vice-versa.

Refactor! Pro provided me with a whack of methods with high CC scores.  In general, methods that have a CC of 15 or higher are strong candidates for refactoring.  CC metrics of 20–30+ should be aggressively refactored to split them up.

Now, while the Refactor! Pro metrics provide a good indication of some hotspots, I wanted to mine out some more information about my code to get a better sense of its overall health and to begin constructing a baseline “map” to evaluate my changes against.  I needed to bring in a heavier duty tool.

Enter: NDepend

NDepend is a static (ie. non-runtime) code/assembly analysis tool for measuring an application's design (recall:  all code is by nature, design) against a series of metrics that gauge type/assembly interdependencies, complexity, stability, couplings, abstraction and cohesion - among many others.  Basically, all the things that help define code that not only functions well, but maintains well. 

While initially a bit intimidating, NDepend can be your best friend once you get around the idiosyncrasies, and is invaluable in putting together a comprehensive picture of how an app is structured.  Initially released as a free tool, it is now quasi-commercial at a cost of $400 USD for a single license.  That said, you can use it for free (with some feature crippling) for non-commercial apps – works for me!

Running the analyses

There are some excellent tutorials on the NDepend site for getting started and how to use the tool, so I won’t go into a deep-dive in this post.  Basically, we want to use the VisualNDepend GUI to create a new project from our VS2005 solution (sorry, no 2003 support) and focus on analyzing just the RNVirtualChessboard and RNChessBoardCommonTypes assemblies – we can remove the RNChessBoard assembly as that contains the code for the control GUI:

At this point, we can now launch the analysis and view the results in the VisualNDepend GUI (click to enlarge):

In the above capture I’ve reset the views in the GUI to focus just on code metrics.  The middle pane with the bubble-blocks is a high-level view of the methods in the assemblies that are organized in relative size to one another according to the current metric, which is set to show cyclomatic complexity.  The scores for CC are in turn provisioned via the CQL queries in the pane just below.

Right.  CQL – That’s pretty cool.  Wait, what?

CQL is an acronym for Content Query Language – in a nutshell, it allows you to run SQL-like queries against the metrics that NDepend has gathered so you can quickly view pertinent results according to adhoc criteria.  OOTB, VisualNDepend has over 60 of these queries that you can run and modify.  This feature alone makes NDepend a tool worth having, IMHO.

Note that we’re seeing only two methods, IsCastleLegit and DoPlayerMove, from the CC query as opposed to the 20–odd that Refactor! Pro was showing.  This is because by default, the CQL query NDepend uses shows the top-10 results for methods with a CC score of 20 or higher.  By editing the query to show methods with CC scores of >= 15, we get ten methods returned:

As cool as this is, we can glean even more targets through NDepend’s additional code quality queries, but for now I’d like to pursue the top-three in this list starting with DoPlayerMove, as I suspect that from here I will touch a lot of other methods.  By right-clicking on the method in the results pane, I can access a context menu for drilling down into dependencies:

From here, I want to know what methods are directly consumed by DoPlayerMove – this query reveals the following shortlist:

Of these, the first two, UpdateMoveBitBoards and GetPieceTypeBitBoard have CC scores of 14 and 15.  Almost immediately we can start to see the broad brushstrokes for our refactoring plan and we’re more aware of the dependencies that we can run up against.

Strategies for Dealing with Cyclomatic Complexity

Because cyclomatic complexity is a measure of the branching and looping elements that exist within a method or type, it makes sense that the strategies we’ll want to employ for refactoring will be concerned with mitigating the effects.  Briefly, this means that we want to look at:

• Branching requirements
• Loop unrolling
• Switch/Case optimizations
• Segmenting code into smaller functions

Additionally, we want to be on the lookout for any low-hanging fruit that will improve the readibility of the code, such as introducing constants for any “magic numbers”, renaming methods where appropriate, collapsing redundant code, etc.

Refactoring-Ho!

For the remainder of the posts, we’ll be going through our target methods to begin sorting them out through the application of various refactorings.  As an aide, I’ll be using the Refactor! Pro add-in to make suggestions on the changes we can make to improve the design of the code.  While we should endeavour to recognize refactoring opportunities in our code without tools, they can provide us productivity gains and be instructive at the same time.  However, as with any power tool, we need to employ a little TFD (thought-first development) and try to do as Norm Abrams recommends and measure twice, cut once.

Note:  If you haven’t already a copy, I highly recommend getting Martin Fowler’s book, Refactoring: Improving the Design of Existing Code.  While it is an older text (1^st edition in 2000) it is the seminal work that defines the reasons and strategies for revising code through the identification and cataloging of “code smells”.  Additionally, you may want to review Joshua Kerievsky's catalog of Refactoring to Patterns as well as Fowler’s online Refactorings Catalog which has current revisions and additions.

If we look at the DoPlayerMove code, we can readily see a number of “low-fruit” opportunities such as this block, which checks for the movement of either white rook as a pre-condition for determining the legality of a special defensive move called castling:

Refactor! Pro has picked up from my selection that I have the opportunity to employ several refactorings, including Replace with Constant – note that it even observed I already have a defined constant for the value that I can use!  Taking a step back, we can also see that there’s an opportunity to employ the Extract Method refactoring:

However, now we’re starting to get ahead of ourselves:  We need to backstop our code with some unit tests so that we can be assured that the changes we’re planning on making don’t break the build or introduce new bugs.  For this, we’ll be using NUnit unit-testing framework v2.4.3 for .NET 2.0 and then adding a new project to our solution for containing our tests, which I’ll be covering in my next post!

In the next installment:  Setting up Unit Tests

Your homework for the next installment is to install and become familiar with NUnit and a complimentary add-in for Visual Studio, TestDriven.NET as I will be covering the fundamentals of each only briefly as they relate to managing and running our tests.  As always, if you have any questions feel free to post them below.

Four years ago I wrote a bit of code to satisfy an "itch" to see what it would take to create a chess engine in C# / .NET 1.1.  Several thousands of lines of code later, it was done and spent a little time up on MSFT's WinForms Code Hero site.  I didn't set out to have it there, mind you - it sort of came up as I was in that fabled "85%" complete zone, and that caused a huge push on my part to get it done within a week to make deadline.

Jump forward to present day:  I've opened up the "crypt" and peered inside my code for the first time in ages.  Cobwebs and other detritus is strewn about - wow.  I actually wrote code like this??

So begins my journey to review my chess control code.  I have a couple of reasons to use it as a guinea pig:  I know that it has some bugs (there's an infamous one that deals with en passant captures), no unit tests and despite the best of intentions isn't that cohesive internally.  It's also .NET 1.1, so I'd like to buff it up to leverage some 2.0 features and eventually 3.5 features. 

The bulk of the code resides in a single class, RNChessRulesEngine.ChessRulesEngine, which is augmented by five helper classes for managing other features (click to enlarge):

ChessRulesEngine is a real monster:  3000+ lines of code, 100+ methods, 40+ member variables and types, excluding arrays of types.  Not all of this is a cause for concern, however:  Validating chess piece moves is a non-trivial exercise that can get complicated fast when we're dealing with bit manipulations, masks, state checks and the like.  Nonetheless, I know that this engine can be improved, especially with respect to improving its maintainability.  Which makes it an excellent candidate for a case study on refactoring existing code.  So, let's move along into the kitchen and see what we'll be using to whip this beast into shape.

The Power Tools

Scrolling up and down through the code, it quickly becomes apparent that despite having written this app, I've long since lost the conceptual mental map for understanding the mechanics.  Further, I'm not even sure where to begin.  There's a few things I'd like to do off the bat, like improving some algebraic coordinate lookup algorithms with arrays, but that's really nibbling 'round the edges.  To be a Code Viking and do Odin's Bidding, I need some power tools:

• NDepend
• Refactor! Pro
• Lutz Roeder's Reflector
• NUnit
• CollabNet's Subversion Code Versioning System
• Visual SVN - Subversion Plugin for Visual Studio

Some of these you probably already have in your kit - these are the core tools that I'll be using to tackle my ancient codebase, and I'll be referring to them in my examples as we take a stroll down my digital memory lane.  I mention them all for the benefit of others who may not be as familiar and curious.

The Motivation:  Maintainability and Cyclomatic Complexity

I've mentioned above that I want to improve the chess rules engine to "modernize" it, and part of this necessitates refactoring the unwieldy portions of the code that are... how to put this delicately...  a bloody nightmare because they're so damn complicated.  I know the routines are complex, because I wrote them.  But how can I be sure which methods to tackle first?  How do I know if my intuitions have any basis in fact?

To answer this question, I'll be leveraging a concept known as cyclomatic complexity (CC), which is a metric that measures how many decisions are taken within a method.  Put another way, it is a count of the following expressions in a method or type:

• if
• while
• foreach
• case
• default
• continue
• goto
• &&
• ||
• catch
• ternary operator (ie. {expression} ? {if true} : {if false} )

In general, the higher the CC metric, the more complex your code, the more of a nightmare it will be to maintain.

Of the tools I've listed above, three provide the ability to measure CC:  NDepend, Refactor! Pro and Reflector (with the separately downloaded Metrics plugin).  I decided to use Refactor! Pro's metrics feature from within Visual Studio to get a handle on what I was in for.  This is easy to get at from the menu:

Clicking Metrics brings up a modal dialog with a list of methods and their related CC, lines of code and maintainability measures.  I filtered on CC and well, now we see where we have to begin looking to make improvements (all supported by unit tests, of course...)

As I've alluded to above, some complexity can't be avoided in this app - but when we look at the DoPlayerMove, IsCastleLegit, and GetInterceptSquares methods with CC scores of 24, 19 and 19 respectively, this tells us where we can begin our investigation and employ some strategies to get those scores down.

Next Steps:  Strategies for Reducing Cyclomatic Complexity

In my next post, I'll be reviewing my next steps for tackling the CC of my top three methods, as well as reviewing some of my other tools that I'll be employing to hack down the problem and get an even greater understanding of what's happening within the rules engine;  for this, I'll be demoing a really fantastic tool, NDepend.  Stay tuned - oh, and Happy Halloween!

Via Larkware I just noticed this excellent web utility that takes the URL-shortening concept pioneered by TinyURL (among many others) and applies a little Web 2.0 secret sauce to convert your baboon ass-ugly addresses into something more in-step with modern web navigation semantics:

After making it "decent" we get:

As the author notes on his site, the advantage DecentURL provides over TinyURL is twofold:  It provides an URL that is disambiguous, human readable and easily communicated to others, and a clear indication of the website where the link redirects.  Unless you turn on the interstitial page for TinyURL, your users get automatically redirected to the target - this can be unnerving to some users.

Pretty cool service - in the "D'oh! Why didn't I think of it first?" category.

Via Bink.nu, news straight outta Redmond that the hitherto model for distributing WSS (ie. a separate, free download vs. OOTB bundle) is being revived.  The reason?

Starting with RC1 and going forward, Windows SharePoint Services 3.0 will have to be downloaded separately. Basically, we made this decision to allow customers to most conveniently obtain the technology while allowing Microsoft to have flexibility in the Windows SharePoint Services development process.

Oookaaaaaay.  I'm not sure how it's going to be more convenient for me to have to download the 70 MB+ install for WSS (excluding SPs, etc.) than have the core version installed by default or at least something that could be configured to install during setup - but that's just me.  Further, WSS was never integrated into the core for Windows Server 2003 - it always was a bolt-on that sat atop the .NET/ASP.NET framework - so, how is this impacting development again?

Maybe recent news on the Windows Server vs. Linux market share front is prompting this decision to encourage even greater penetration - but WSS seems like a no-brainer for the environments that Windows Server will be installed against, especially if you're giving it away and using it as a loss-leader to get MOSS 2007 in the back-door.