Lookup - .NET's hidden gem

.NET Framework has a lot to offer when comes to generic data structures, especially collections. We have several lists, arrays, sets, dictionaries - each of them has its performance and functional characteristics and scenarios where it fits much better than the others. As I'm observing in the project I work in, one of the most often forgotten yet powerful type of collection is Lookup. I think it needs more attention.

ILookup was introduced to the framework as a part of LINQ and is exclusively used in LINQ context, as a result of ToLookup calls. Logically, it is a key-value collection like IDictionary, but it is designed to hold multiple values in a single key. Also, unlike Dictionary<K, V>, it is immutable, what means that after creating the lookup, we can only read it - no modifications are possible.

Generally one may say that ILookup<K, V> is no better than IDictionary<K, IEnumerable<V>> and as such is redundant. But I'd strongly disagree. First of all, let's think how are dictionaries of collections used. From my experience, it's most often used to keep predefined static "dictionaries" that are loaded once and live long to provide easy access to some rarely changing values like what counties are there in each country etc. Well, these are even often called "lookup tables". Note that in most cases we don't ever change the stored values - it is immutable. We replace it as a whole periodically or when something changes. Doesn't it sound exactly like ILookup<K, V> key features discussed above? We should always be using the tools that are best suited for the job to avoid reinventing the wheel and avoid the problems others already solved.

Moreover, ILookup's definition is clearly more readable than nested generics in its dictionary-based equivalent. When I look at the code never seen before and I see ILookup<K, V>, I instantly know that it is the lookup table and I feel its read-only, one-way nature. When I see IDictionary<K, IEnumerable<V>> I need to consider the possibility that it is used as a read-write store for some values and I, as a user of this code, can (or should?) modify that collection. Using Lookup for lookups just makes sense.

IDictionary-based lookups, as mutable data structures may kick us badly. I've once experienced quite an ugly error caused by passing around the plain List<T> read from what was intended to be static lookup shared between users and was based on Dictionary<K, List<V>>. The intention was to pass around the immutable lookup data, but the receiving code actually got mutable list being exactly the same reference that was sitting in the global lookup. The value passed was eventually customized for each user and there were miracles happening to the global lookup. All that would be just impossible with lookups.

With dictionaries that are open for modification and not thread-safe by default, we are also subject to multiple kinds of failures in multi-threaded scenarios. All of it is gone with immutable data structure like ILookup.

And last but not least - null checks. Who likes to litter his code with all that boring null checks? When using IDictionary as a lookup table, every piece of code that consumes its data need to check for key existence first or have a conditional statement with TryGetValue method, because calling dictionary[nonExistingKey] would throw dreadful KeyNotFoundException. Moreover, even if the key exists, the value may still legally be null, so to read the collection contained under the key we need to have two checks:

if (dictionary.ContainsKey(theKey))
{
     var collectionOrPossiblyNull = dictionary[theKey];
     if (collectionOrPossiblyNull != null)
     {
          DoSomethingWithValues(collectionOrPossiblyNull);
     }
}

or, with more compactness but same complexity:

T collection;
if (dictionary.TryGetValue(theKey, out collection) && collection != null)
     DoSomethingWithValues(collection);

ILookup<K, V> was designed totally differently around key existence and null values. It just returns an empty collection for non-existent keys. And thanks to its strictly controlled way of creating (by LINQ's ToLookup method only), we can also be sure that no null collection is possible. And the code above just looks as it should like:

DoSomethingWithValues(lookup[theKey]);

Isn't it beautiful?

Next time I'll try to find some pitfalls or inconveniences of using lookups.

Me & Open Source - a New Year's Resolution

I am working as a software developer full-time for several years now. I've already written many thousands of lines of code, but nearly none of it is publicly available. Most of it remains a property of my employers for who the code was created, but there are always some pieces that are already open source or side projects that don't need to adhere to strict ownership rules and can be generalized enough to be shared with others.

I always wanted to share and I had hundreds of ideas for full-size projects that I could do when there's enough time. But in the reality, there was never enough time and motivation for anything big. Full-time job takes a lot of time, the rest goes to family and other duties. But there is always a few late evening hours each week that can be saved.

All the things I've shared with the community up to date were mentioned here on my blog. These were mostly short gists or snippets. The only larger thing was an HTML building API based on the "loquacious" interface idea, published on GitHub as NOtherHtml. I still love the design! But I admit, it was rather one-timer, not a major contribution to the open source world.

So, here is my New Year's Resolution for 2014: try spending those few late evening hours on contributing to the open source projects. Yeah, I know no one cares, but I'm sharing it as posting it publicily will motivate me more than leaving it just as my internal thought. There will be probably no biggies for the reasons mentioned, I think I'll rather focus on bug fixes or small features for the projects I use. It's easiest, it's beneficial, it's fair.

As a start, yesterday I've submitted my first pull request to the "real" open source project I use - JP. Boodhoo's developwithpassion.specifications. I've fixed a bug in the extension method that helps assert collections elements equality, but failed when the collections were of different lengths. I feel I'm already over the hump!

ASP.NET MVC: Current route values implicitly used by Url.Action

I really don't like when I work with statically-typed language like C# and still need to rely on strings or other loosely-typed constructs for things that may be strongly-typed. ASP.NET MVC went its way towards strongly-typing and now offers things like strongly-typed view models, but still lacks official built-in support for building internal links and URLs without using plain controller and action strings.

Fortunately, here is where MVC Futures comes in (available on NuGet for MVC 3 or 4). It offers a nice expression-based extension methods to build links (on HtmlHelper):

Html.ActionLink<TheController>(c => c.TheAction(theParam))

and URLs (on UrlHelper):

Url.Action<TheController>(c => c.TheAction(theParam))

It's working fine and it protects me from working with those ugly string-based methods and it is also a very convenient way to specify the target action parameters - in definitely nicer way then manually building the RouteValuesCollection required by those traditional methods.

But there is one not well-known feature of MVC (at least I haven't heard a lot about it) that for me seems to be disturbing here - MVC is reusing the route values from the current request when building URLs and no other value specified. This maybe makes some sense for the string-based methods (you don't need to build those RouteValuesCollections over and over again), but it makes no sense for the expression-based approach as the compiler enforces specifying all the parameters explicitly in order to build a lambda expression that compiles.

And here comes the nasty bug I've recently spent some hours on - passing null value is like not passing a value at all. MVC puts null under the appropriate key in the RouteValuesCollection, it then goes down to Route.GetVirtualPath method, which also takes the current route values from the RequestContext. And then the evil happens - the low-level System.Web.Routing's method ParsedRoute.Bind ignores the null value and - bang - it takes the value from the current request, if any accidentally matches by the parameter name.

It means that when trying to build an URL that passes parameter param equal to null and the current request accidentally have parameter named also param (regardless of its type or existence of any logical connection), the request's param value will be passed instead our explicitly demanded null value. And I can see no way to pass null in this case.

Actually, the bug (or feature?) exists in case of string-based URL builder methods, too. But here it is much more visible and obviously wrong.

The only way to fix that strange implicit parameter inheritance by name I know is to work around it - either by removing the name collision by renaming one of the parameters (yuck!) or by using own extension method.

I've created my own extension method to generate URLs/links that has the same signature as the buggy ones and placed it in the namespace more visible than those replaced (you'd better check your usings carefully). Here is the UrlHelper extension I have - HtmlHelper implementation generally calls UrlHelper and wraps its result in a link, so I'll omit it here. The method calls the same methods as the original method being replaced, but it tweaks the RequestContext instance: instead of passing the instance available in UrlHelper (which contains those conflicting route values from the current request), I'm creating new RequestContext reusing Route and IRouteHandler instances from the current request, leaving the actual route values empty. This way there's no possibility for the current values to "infect" our URL building process anymore. Interesting is that RouteData constructor doesn't enforce the values being set, anyway.

public static string Action<TController>(this UrlHelper helper, Expression<Action<TController>> action)
    where TController : Controller
{
    // we need to recreate RequestContext without values, to override the MVC "feature"
    // that replaces null specified in action with value inherited from current request
    var currentRouteData = helper.RequestContext.RouteData;
    var fixedRouteData = new RouteData(currentRouteData.Route, currentRouteData.RouteHandler);
    var fixedRequestContext = new RequestContext(helper.RequestContext.HttpContext, fixedRouteData);

    var valuesFromExpr = Microsoft.Web.Mvc.Internal.ExpressionHelper.GetRouteValuesFromExpression(action);
    var vpd = helper.RouteCollection.GetVirtualPathForArea(fixedRequestContext, valuesFromExpr);
    return vpd == null ? null : vpd.VirtualPath;
}

Well, it seems to be yet another example of the fact that null is rather vague and problematic thing. It can represent many different notions, depending on the context and implementation - like no value, empty value, inherited value etc. Althouth ASP.NET MVC treats null as "inherit the value" not only in this case, I'd always prefer being explicit about that kind of behaviors.

On Abstractions in Requirements

We, as a software developers, are used to work with abstractions and to strive to work with abstractions rather than with specific implementation details. We always try to build the abstraction layers on top of complicated rules and design our systems so that the details are hidden at low levels. The system, looking from some distance, is built from nice generic bricks.

But we're much less used to have our abstractions in line what our business requirements are and how the stakeholders look at it. We're often thinking about abstractions only on technical, source code level. But ideally, if something is really a well-designed abstraction, it should serve everyone equally well.

Know the abstractions the customers use

When building the software for a particular group of users, they probably have some ideas how things should work and how things relate to each other. Ask your customers not only for the details you need to have to complete your concrete implementation, but also ensure you know the bigger picture. If your customers define some rules, before implementing it, get the knowledge what these rules are about and what they represent. These rules probably result from some customers' business concept and it will appear in multiple requirements or ideas over and over again. Knowing the concept upfront will save some time finding duplicated rules and/or inventing the abstractions on your own. If not identified early enough, introducing it to the codebase later will probably mean conflicts with existing, made up abstractions.

Agree with customers on the abstractions

Don't introduce high-level abstraction for things that sounds similiar if your customers don't use those things together. When the product evolves, this kind of abstraction will probably end up as a gordian knot tying two things that are meant to go different ways. Eventually you'll have to remove the abstraction on the way (which may not be easy) or some dirty hacks will grow around it.

Talk with everyone about naming

Naming is one of the most difficult thing in programming, right? So why not rely on our customers. They probably know better how to name the things they are familiar with. Discuss the synonyms and agree on the naming before introducing the abstraction to the codebase. It may be a good idea to have a glossary of terms the customers use and how it's represented in the codebase so that different developers (but also managers, technical writers, customer support, etc. - essentially all the stakeholders) don't use another synonym for the same thing. This will avoid confusion and misunderstanding. Moreover, mapping of "documents" to "articles" through "news stories" will be weird, anyway.

Don't use details when there's an abstraction agreed

Whoever create the requirements for your project, they should be aware you know the concepts they use, so that they will use it in the communication, for everyone's convenience. Subsequent requirements should not repeat the definition of the abstraction in detail, but rely on the fact you already know it. Otherwise it will probably end up inconsistent or implemented locally, separately from the previously introduced abstractions. When the existing concept's definition turns out to be an obstacle and it needs to be clarified with details later in the project's development, it probably means that either there is no real abstraction there or the abstraction is not defined or understood correctly by all parties.

Make sure you have proper number of well understood abstractions

Abstractions should be - well - abstract enough. It means that it should be easy to grasp it and explain it to a new team member or new customer representative. If it's not - it's probably not a high-level abstraction. There are also practical limits how many high-level abstractions make sense in the project. If there are too many, so that they can't be learned easily, either the project is overcomplicated or - again - these are not really high-level abstractions.

This all may sound obvious, but I've recently experienced it isn't. In our project, there was a high-level decision made that we need to have our content categorized. The idea of the categories went through several layers of business analysts and subject-matter experts and before it get to the development team, it became fuzzy and the general concept flittered away. We get nothing about categories, but a bunch of seemingly unrelated yet not trivial requirements to "move things around here and there". We implemented it as so rather thoughlessly. And some time later there was a business decision that things should work together as they are related. But that "related" thing doesn't exist for us at all - we have several own concepts of "relations" instead, grown on the developers' need for abstractions. And now we need to go few big steps back to align. Oops!

The Alternative Development Methodologies Glossary

Have you ever wondered what all those TDDs, BDDs, DDDs, ATDDs mean? Are you sure your project is following all these methodologies that form the software development mainstream? Do you know what to do to stay up to date?

Here is the comprehensive and exhaustive list of various established development techniques that you can meet (or have a chance to introduce) in your project. Feel free to be inspired and use as many -DDs as you can!

ADD: Anticipation Driven Development

When the requirements are carefully hidden in stakeholders' minds and not shared with the development team until the deadline. In that methodology developers need to be ready for everything.

BDD: Bug Driven Development

Delivering anything as quick as possible and explaining all the missing features as "just bugs". Then fixing it using a mix of magic and dirty hacks.

CDD: Copy-Paste Driven Development

Introducing new feature to the system is easy as long as the feature may be put together from the borrowed parts of other features. Low coupling, sort of.

DDD: Development Driven Development

Have you ever had an impression that the project's code just live its own life?

EDD: Email Driven Development

As a productivity improvement technique, developers are expected to reduce wasting time in those ugly black IDEs and keep focused on the real stuff being discussed via email. 60 times a day.

FDD: Frustration Driven Development

After delivering the final requirements, implementing and making the code well-factored and production-ready, the new final (finaler) requirements arrive, without changing the deadline. And then, two weeks later, there are the finalest requirements.

GDD: Google Driven Development

Let's google it up. All the code is already there, for sure.

HDD: Hardcoding Driven Development

KISS and YAGNI plus being extremely explicit everywhere. So explicit that any business logic or calculations makes a smell. May also be the Test Driven Development that went too far (the code works only for cases used in the tests, because all the answers are hardcoded).

IDD: Idiot Driven Development

Self-explaining. But don't use that name when talking to your boss.

JDD: Job Security Driven Development

The primary goal each developer seems to have is to become indispensable. It's easy to do when adhering to several simple rules. That technique encourages great productivity of developers (when counted in lines of code written).

KDD: Knot Driven Development

From the Gordian Knot - when the cyclomatic complexity is higher than the number of lines. And when all the special cases are covered with enough attention and care.

LDD: Layering Driven Development

The technique focused on proper code encapsulation and isolation - each developer creates his/her own layer of abstraction. Who wants to work with that legacy code, anyway?

MDD: Meeting Driven Development

Methodology that relies on the premise that each development problem may be solved by discussing it over and over regularly in the adequately large group for the adequately long time. And if it still doesn't succeed, invite even more managers.

NDD: Not Driven Development

IDD with the principle of team self-organization.

ODD: Outlook Driven Development

See EDD. Syntax coloring plugin for Outlook would be nice. And also source control plugin, to be able to commit the code by email, finally.

PDD: Patch Driven Development

When the development is time-constrained, with fixed date, anything should be always deployed to production on time, regardless on its development status. Then there's a patching phase, that is trying to understand what was deployed and replacing it with working bits by some shotgun surgeries.

QDD: Quick-Fix Driven Development

Mix of Patch Driven Development, TODO Driven Development and some hope.

RDD: Refukctoring Driven Development (officially: Refactoring Driven Development)

When it's not possible to isolate the crappy code written last year (see FDD), comment it out and leave with "TODO" flag. Then write it once again.

SDD: Showcase Driven Development

Don't do anything unless there's a customer showcase tomorrow. Then rigorously apply QDD and TDD.

TDD: TODO Driven Development

Project planning methodology that assumes the existence of some time in the project's future when there will be no new feature requests or bugs and the developers will have a lot of time to reduce the technical debt.

UDD: Utopia Driven Development

Pragmatics' name for TODO Driven Development.

VDD: Versatility Driven Development

The methodology about developing a solution for every single customer need (including those not yet discovered) at once, by a single project. Also the way of writing code so that it can be re-configured to do other things in the future, if the need arises. Also known as Soft Coding.

WDD: Wheel-Reinventing Driven Development

The concept based on natural and inborn lack of trust for others' code, including guys next room. Instead of taking a risk of using others' code, let's write it from the scratch again (and use both versions in the same project in the same time). Sort of loose coupling, again.

XDD: Xero Driven Development

Mutation of CDD. The only features possible to implement are those like already implemented. We need to have some strong foundations to copy from, right?

YDD: Yesterday Driven Development

Pretty broadly used time management methodology in software development. All tasks are due two days before tomorrow.

ZDD: Zen Driven Development

Software development and mind training at once. Occurs when the codebase requires "the attainment of enlightenment and the personal expression of direct insight" to work with.

Let me know if I forgot anything from the mainstream.

Liskov Substitution Principle vs. immutability

Today I had a very interesting discussion about Liskov Substitution Principle (LSP) - what it really means and how to avoid breaking it, of course using an overused example of squares and rectangles. Liskov's principle tells us to design our inheritance trees or interface implementations in such a way that whenever the code uses the base class (or interface), any of the derived classes (implementations) can be used without breaking existing behavior or invariants. In wider understanding, it also means that whenever we use an abstraction like base class or interface, we should not expect any particular implementation provided in the runtime nor should we know anything about that implementations. This also forbids any constructs like conditions based on implementation's concrete type - if we need it, we're working with leaky abstraction that need to be rethought and not hacked around.

void MethodThatGetsAbstraction(IAbstraction abstraction)
{
    if (abstraction is SomethingReal)
        YouReDoingItWrong();
}

Let me remind the classical example of shapes I've mentioned before. As we know, squares are rectangles, and we often represent "is a" relationships like this in code using an inheritance - Square derives from Rectangle (I don't want to discuss here whether it makes sense or not, but the fact is this IS the most often quoted example when talking about LSP). A rectangle, mathematically speaking, is defined by its side sizes. We can represent these as properties in our Rectangle class. We also have a method to calculate an area of our rectangle:

public class Rectangle
{
    public int Height { get; set; }
    public int Width { get; set; }

    public int CalculateArea()
    {
        return Height * Width;
    }
}

Now enter the Square. It is a special case of rectangle that has both sides of equal lengths. We implement it by setting the Height to equal Width whenever we set Width and opposite. Now consider the following test:

class When_calculating_rectangle_area
{
    [Test]
    public void It_should_calculate_area_properly()
    {
        // arrange
        var sut = new Rectangle();
        sut.Width = 2;
        sut.Height = 10;
        
        // act
        var result = sut.CalculateArea();

        // assert
        Assert.Equal(result, 20);
}

It works perfectly fine until, according to the ability given us by the Liskov's principle, we change Rectangle into its derived class, Square (and leave the rest unchanged, again according to the LSP). Note that in real-life scenarios we rarely create the Rectangle a line above, we got it created somewhere and we probably don't even know its specific runtime type.

class When_calculating_square_area
{
    [Test]
    public void It_should_calculate_area_properly()
    {
        // arrange
        var sut = new Square();
        sut.Width = 2; // also sets Height behind the scenes
        sut.Height = 10; // also sets Width behind the scenes, overriding the previous value
        
        // act
        var result = sut.CalculateArea();

        // assert
        Assert.Equal(result, 20); // naah, we have 100 here
}

Square inheriting from Rectangle breaks the LSP badly by strenghtening the base class' preconditions in a subtype - base class doesn't need an equal sides, it's the implementation-specific whim we don't even know about if we're only providing the base class to be derived in the wild. But what is the root cause of that failure? It's the fact that Square is not able to enforce its invariants (both sides equal) properly. It couldn't yell by throwing an exception whenever one tries to set the height differently than width, because one may set width earlier than height - and we definitely don't want to enforce particular property setting order, right?. Setting width and height atomically would solve that problem - consider the following code:

public class Rectangle
{
    private int _height;
    private int _width;

    public virtual int SetDimensions(int height, int weight)
    {
        _height = height;
        _width = width;
    }

    public int CalculateArea()
    {
        return _height * _width;
    }
}

public class Square : Rectangle { public override int SetDimensions(int height, int weight) { if (height != width) throw new InvalidOperationException("That's a weird square, sir!"); _height = _width = height; } } But now we've replaced one LSP abuse with another. How the poor users of Rectangle can be prepared for SetDimensions throwing an exception? Again, it's an implementation-specific weirdness, we don't want our abstraction to know about it, as it will become a pretty leaky one. But is width and height really a state? I'd rather say they are shape's identity - if they change, we are talking about another shape than before. So why expose setting possibility at all? This leads us to the simple but extremely powerful concept of immutability - a concept in which the object's data once set cannot be changed and are read-only. The only way to populate an immutable object with data is to do it when creating the object - in its constructor. Note that constructors are not inherited and when new-ing a Rectangle we are 100% sure it's not Square or any other unknown beast, and conversely, when constructing Square we can enforce our invariants without an influence on base class behaviours - as all properly constructed Squares will be valid Rectangles.

public class Rectangle
{
    private int _height;
    private int _width;

    public Rectangle(int height, int weight)
    {
        _height = height;
        _width = width;
    }

    public int CalculateArea()
    {
        return _height * _width;
    }
}

public class Square : Rectangle
{
    public Square(int size)
        : base(size, size)
    {
    }
}

LSP satisfied, code clean, nasty bugs and leaky abstractions removed - immutability is king!

Code Smells: Rigidity

I was recently preparing a small talk about several code smells, as discussed by Robert C. Martin in his famous 'Clean Code' book. I've decided to share my notes - it's nothing revolutionary, a bit of copy-paste from well-known resources and a bit of my personal comments and understandings.

The one for today is rigidity. Rigidity literally means "the inability to change or be changed to fit changed circumstances". And that nicely fits what the smell is about: "The software is difficult to change. A small change causes a cascade of subsequent changes". We all know it - some tasks that sounded easy at the beginning became a few weeks of bug hunting or turned out to be too difficult to finish without destroying everything around.

When it happens?

• When the code is written in procedural style - a.k.a. "everything in one place" - with a lot of very narrow and specific, possibly unrelated conditions and special cases handling included directly in the "main" method,
• When there is a lack of abstractions - meaning that the code operates on the low level of technical details instead of focusing on more real-life concepts, like bit flags fiddling to check for object's characteristics instead of having it available as a method or a property,
• When the code implements some general concepts, but defines it with details specific to particular use case - like a code to render an HTML table from the general matrix that also decides the table header has dark background,
• When a single responsibility is spread between many classes or code layers - like checking user's permissions on every layer from the data access layer up to the UI layer,
• When components need to know a lot of details about each other to communicate properly (leaky abstractions).

How to avoid it?

• Thinking in general terms, wrapping the implementation details into abstractions that are understood on less technical levels,
• Creating code with satisfying the requirements first in mind, not what API's we're using or the constraints we have around,
• Using object-oriented techniques and SOLID - with its small classes, single responsibilities and open design,
• Encapsulating the code in the logical pieces, defining a clear boundaries and interfaces between them - if you can't tell what is the border of responsibilities, it's probably done wrong,
• Depending upon abstraction, not implementation.