All posts by jonskeet

Mad props to @arcaderage for the "Princess Rescue" image - see https://toggl.com/programming-princess for the full original
C#, Edulinq, LINQ

Reimplementing LINQ to Objects: Part 6 – Repeat

2 Comments

A trivial method next, with even less to talk about than "Empty"… "Repeat". This blog post is merely a matter of completeness.

What is it?

"Repeat" is a static, generic non-extension method with a single overload:

public static IEnumerable<TResult> Repeat<TResult>(
    TResult element,
    int count)

It simple returns a sequence which contains the specified element, repeated "count" times. The only argument validation is that "count" has to be non-negative.

What are we going to test?

There’s really not a lot to test here. I’ve thought of 4 different scenarios:

  • A vanilla "repeat a string 3 times" sequence
  • An empty sequence (repeat an element 0 times)
  • A sequence containing null values (just to prove that "element" can be null)
  • A negative count to prove that argument validation occurs, and does so eagerly.

None of this is remotely exciting, I’m afraid.

Let’s implement it!

Just about the only thing we could do wrong here is to put the argument validation directly in an iterator block… and we’ve implemented the "split method" pattern so many times already that we wouldn’t fall into that trap. So, here’s the code in all its tedious lack of glory:

public static IEnumerable<TResult> Repeat<TResult>(TResult element, int count)
{
    if (count < 0)
    {
        throw new ArgumentOutOfRangeException("count");
    }
    return RepeatImpl(element, count);
}

private static IEnumerable<TResult> RepeatImpl<TResult>(TResult element, int count)
{
    for (int i = 0; i < count; i++)
    {
        yield return element;
    }
}

That’s it. Um, interesting points to note… none.

Conclusion

There’s no sense in dragging this out. That’s the lot. Next up, Count and LongCount – which actually do have a couple of interesting points.

C#, Edulinq, LINQ

Reimplementing LINQ to Objects: Part 5 – Empty

14 Comments

Continuing with the non-extension methods, it’s time for possibly the simplest LINQ operator around: "Empty".

What is it?

"Empty" is a generic, static method with just a single signature and no parameters:

public static IEnumerable<TResult> Empty<TResult>()

It returns an empty sequence of the appropriate type. That’s all it does.

There’s only one bit of interesting behaviour: Empty is documented to cache an empty sequence. In other words, it returns a reference to the same empty sequence every time you call it (for the same type argument, of course).

What are we going to test?

There are really only two things we can test here:

  • The returned sequence is empty
  • The returned sequence is cached on a per type argument basis

I’m using the same approach as for Range to call the static method, but this time with an alias of EmptyClass. Here are the tests:

[Test]
public void EmptyContainsNoElements()
{
    using (var empty = EmptyClass.Empty<int>().GetEnumerator())
    {
        Assert.IsFalse(empty.MoveNext());
    }
}

[Test]
public void EmptyIsASingletonPerElementType()
{
    Assert.AreSame(EmptyClass.Empty<int>(), EmptyClass.Empty<int>());
    Assert.AreSame(EmptyClass.Empty<long>(), EmptyClass.Empty<long>());
    Assert.AreSame(EmptyClass.Empty<string>(), EmptyClass.Empty<string>());
    Assert.AreSame(EmptyClass.Empty<object>(), EmptyClass.Empty<object>());

    Assert.AreNotSame(EmptyClass.Empty<long>(), EmptyClass.Empty<int>());
    Assert.AreNotSame(EmptyClass.Empty<string>(), EmptyClass.Empty<object>());
}

Of course, that doesn’t verify that the cache isn’t per-thread, or something like that… but it’ll do.

Let’s implement it!

The implementation is actually slightly more interesting than the description so far may suggest. If it weren’t for the caching aspect, we could just implement it like this:

// Doesn’t cache the empty sequence
public static IEnumerable<TResult> Empty<TResult>()
{
    yield break;
}

… but we want to obey the (somewhat vaguely) documented caching aspect too. It’s not really hard, in the end. There’s a very handy fact that we can use: empty arrays are immutable. Arrays always have a fixed size, but normally there’s no way of making an array read-only… you can always change the value of any element. But an empty array doesn’t have any elements, so there’s nothing to change. So, we can reuse the same array over and over again, returning it directly to the caller… but only if we have an empty array of the right type.

At this point you may be expecting a Dictionary<Type, Array> or something similar… but there’s another useful trick we can take advantage of. If you need a per-type cache and the type is being specific as a type argument, you can use static variables in a generic class, because each constructed type will have a distinct set of static variables.

Unfortunately, Empty is a generic method rather than a non-generic method in a generic type… so we’ve got to create a separate generic type to act as our cache for the empty array. That’s easy to do though, and the CLR takes care of initializing the type in a thread-safe way, too. So our final implementation looks like this:

public static IEnumerable<TResult> Empty<TResult>()
{
    return EmptyHolder<TResult>.Array;
}
        
private static class EmptyHolder<T>
{
    internal static readonly T[] Array = new T[0];       
}

That obeys all the caching we need, and is really simple in terms of lines of code… but it does mean you need to understand how generics work in .NET reasonably well. In some ways this is the opposite of the situation in the previous post – this is a sneaky implementation instead of the slower but arguably simpler dictionary-based one. In this case, I’m happy with the trade-off, because once you do understand how generic types and static variables work, this is simple code. It’s a case where simplicity is in the eye of the beholder.

Conclusion

So, that’s Empty. The next operator – Repeat – is likely to be even simpler, although it’ll have to be another split implementation…

Addendum

Due to the minor revolt over returning an array (which I still think is fine), here’s an alternative implementation:

public static IEnumerable<TResult> Empty<TResult>()
{
    return EmptyEnumerable<TResult>.Instance;
}

#if AVOID_RETURNING_ARRAYS
private class EmptyEnumerable<T> : IEnumerable<T>, IEnumerator<T>
{
    internal static IEnumerable<T> Instance = new EmptyEnumerable<T>();

    // Prevent construction elsewhere
    private EmptyEnumerable()
    {
    }

    public IEnumerator<T> GetEnumerator()
    {
        return this;
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this;
    }

    public T Current
    {
        get { throw new InvalidOperationException(); }
    }

    object IEnumerator.Current
    {
        get { throw new InvalidOperationException(); }
    }

    public void Dispose()
    {
        // No-op
    }

    public bool MoveNext()
    {
        return false; // There’s never a next entry
    }

    public void Reset()
    {
        // No-op
    }
}

#else
private static class EmptyEnumerable<T>
{
    internal static readonly T[] Instance = new T[0];       
}
#endif

Hopefully now everyone can build a version they’re happy with :)

C#, Edulinq, LINQ

Reimplementing LINQ to Objects: Part 4 – Range

12 Comments

This will be a short post, and there’ll probably be some more short ones coming up too. I think it makes sense to only cover multiple operators in a single post where they’re really similar. (Count and LongCount spring to mind.) I’m in your hands though – if you would prefer "chunkier" posts, please say so in the comments.

This post will deal with the Range generation operator.

What is it?

Range only has a single signature:

public static IEnumerable<int> Range(
    int start,
    int count)

Unlike most of LINQ, this isn’t an extension method – it’s a plain old static method. It returns an iterable object which will yield "count" integers, starting from "start" and incrementing each time – so a call to Enumerable.Range(6, 3) would yield 6, then 7, then 8.

As it doesn’t operate on an input sequence, there’s no sense in which it could stream or buffer its input, but:

  • The arguments need to be validated eagerly; the count can’t be negative, and it can’t be such that any element of the range could overflow Int32.
  • The values will be yielded lazily – Range should be cheap, rather than creating (say) an array of "count" elements and returning that.

How are we going to test it?

Testing a plain static method brings us a new challenge in terms of switching between the "normal" LINQ implementation and the Edulinq one. This is an artefact of the namespaces I’m using – the tests are in Edulinq.Tests, and the implementation is in Edulinq. "Parent" namespaces are always considered when the compiler tries to find a type, and they take priority over anything in using directives – even a using directive which tries to explicitly alias a type name.

The (slightly ugly) solution to this that I’ve chosen is to include a using directive to create an alias which couldn’t otherwise be resolved – in this case, RangeClass. The using directive will either alias RangeClass to System.Linq.Enumerable or Edulinq.Enumerable. The tests then all use RangeClass.Range. I’ve also changed how I’m switching between implementations – I now have two project configurations, one of which defines the NORMAL_LINQ preprocessor symbol, and the other of which doesn’t. The RangeTest class therefore contains:

#if NORMAL_LINQ
using RangeClass = System.Linq.Enumerable;
#else
using RangeClass = Edulinq.Enumerable;
#endif

There are alternatives to this approach, of course:

  • I could move the tests to a different namespace
  • I could make the project references depend on the configuration… so the "Normal LINQ" configuration wouldn’t reference the Edulinq implementation project, and the "Edulinq implementation" configuration wouldn’t reference System.Core. I could then just use Enumerable.Range with an appropriate using directive for System.Linq conditional on the NORMAL_LINQ preprocessor directive, as per the other tests.

I like the idea of the second approach, but it means manually tinkering with the test project file – Visual Studio doesn’t expose any way of conditionally including a reference. I may do this at a later date… thoughts welcome.

What are we going to test?

There isn’t much we can really test for ranges – I only have eight tests, none of which are particularly exciting:

  • A simple valid range should look right when tested with AssertSequenceEqual
  • The start value should be allowed to be negative
  • Range(Int32.MinValue, 0) is an empty range
  • Range(Int32.MaxValue, 1) yields just Int32.MaxValue
  • The count can’t be negative
  • The count can be zero
  • start+count-1 can’t exceed Int32.MaxValue (so Range(Int32.MaxValue, 2) isn’t valid)
  • start+count-1 can be Int32.MaxValue (so Range(Int32.MaxValue, 1) is valid)

The last two are tested with a few different examples each – a large start and a small count, a small start and a large count, and "fairly large" values for both start and count.

Note that I don’t have any tests for lazy evaluation – while I could test that the returned value doesn’t implement any of the other collection interfaces, it would be a little odd to do so. On the other hand, we do have tests which have an enormous count – such that anything which really tried to allocate a collection of that size would almost certainly fail…

Let’s implement it!

It will surely be no surprise by now that we’re going to use a split implementation, with a public method which performs argument validation eagerly and then uses a private method with an iterator block to perform the actual iteration.

Having validated the arguments, we know that we’ll never overflow the bounds of Int32, so we can be pretty casual in the main part of the implementation.

public static IEnumerable<int> Range(int start, int count)
{
    if (count < 0)
    {
        throw new ArgumentOutOfRangeException("count");
    }
    // Convert everything to long to avoid overflows. There are other ways of checking
    // for overflow, but this way make the code correct in the most obvious way.
    if ((long)start + (long)count – 1L > int.MaxValue)
    {
        throw new ArgumentOutOfRangeException("count");
    }
    return RangeImpl(start, count);
}

private static IEnumerable<int> RangeImpl(int start, int count)
{
    for (int i = 0; i < count; i++)
    {
        yield return start + i;
    }
}

Just a few points to note here:

  • Arguably it’s the combination of "start" and "count" which is invalid in the second check, rather than just count. It would possibly be nice to allow ArgumentOutOfRangeException (or ArgumentException in general) to blame multiple arguments rather than just one. However, using "count" here matches the framework implementation.
  • There are other ways of performing the second check, and I certainly didn’t have to make all the operands in the expression longs. However, I think this is the simplest code which is clearly correct based on the documentation. I don’t need to think about all kinds of different situations and check that they all work. The arithmetic will clearly be valid when using the Int64 range of values, so I don’t need to worry about overflow, and I don’t need to consider whether to use a checked or unchecked context.
  • There are also other ways of looping in the private iterator block method, but I think this is the simplest. Another obvious and easy alternative is to keep two values, one for the count of yielded values and the other for the next value to yield, and increment them both on each iteration. A more complex approach would be to use just one loop variable – but you can’t use "value < start + count" in case the final value is exactly Int32.MaxValue, and you can’t use "value <= start + count – 1" in case the arguments are (int.MinValue, 0). Rather than consider all the border cases, I’ve gone for an obviously-correct solution. If you really, really cared about the performance of Range, you’d want to investigate various other options.

Prior to writing up this post, I didn’t have good tests for Range(Int32.MaxValue, 1) and Range(Int32.MinValue, 0)… but as they could easily go wrong as mentioned above, I’ve now included them. I find it interesting how considering alternative implementations suggests extra tests.

Conclusion

"Range" was a useful method to implement in order to test some other operators – "Count" in particular. Now that I’ve started on the non-extension methods though, I might as well do the other two (Empty and Repeat). I’ve already implemented "Empty", and will hopefully be able to write it up today. "Repeat" shouldn’t take much longer, and then we can move on to "Count" and "LongCount".

I think this code is a good example of situations where it’s worth writing "dumb" code which looks like the documentation, rather than trying to write possibly shorter, possibly slightly more efficient code which is harder to think about. No doubt there’ll be more of that in later posts…

C#, Edulinq, LINQ

Reimplementing LINQ to Objects: Part 3 – “Select” (and a rename…)

9 Comments

It’s been a long time since I wrote part 1 and part 2 of this blog series, but hopefully things will move a bit more quickly now.

The main step forward is that the project now has a source repository on Google Code instead of just being a zip file on each blog post. I had to give the project a title at that point, and I’ve chosen Edulinq, hopefully for obvious reasons. I’ve changed the namespaces etc in the code, and the blog tag for the series is now Edulinq too. Anyway, enough of the preamble… let’s get on with reimplementing LINQ, this time with the Select operator.

What is it?

Like Where, Select has two overloads:

public static IEnumerable<TResult> Select<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, TResult> selector)

public static IEnumerable<TResult> Select<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, int, TResult> selector)

Again, they both operate the same way – but the second overload allows the index into the sequence to be used as part of the projection.

Simple stuff first: the method projects one sequence to another: the "selector" delegate is applied to each input element in turn, to yield an output element. Behaviour notes, which are exactly the same as Where (to the extent that I cut and paste these from the previous blog post, and just tweaked them):

  • The input sequence is not modified in any way.
  • The method uses deferred execution – until you start trying to fetch items from the output sequence, it won’t start fetching items from the input sequence.
  • Despite deferred execution, it will validate that the parameters aren’t null immediately.
  • It streams its results: it only ever needs to look at one result at a time.
  • It will iterate over the input sequence exactly once each time you iterate over the output sequence.
  • The "selector" function is called exactly once per yielded value.
  • Disposing of an iterator over the output sequence will dispose of the corresponding iterator over the input sequence.

What are we going to test?

The tests are very much like those for Where – except that in cases where we tested the filtering aspect of Where, we’re now testing the projection aspect of Select.

There are a few tests of some interest. Firstly, you can tell that the method is generic with 2 type parameters instead of 1 – it has type parameters of TSource and TResult. They’re fairly self-explanatory, but it means it’s worth having a test for the case where the type arguments are different – such as converting an int to a string:

[Test]
public void SimpleProjectionToDifferentType()
{
    int[] source = { 1, 5, 2 };
    var result = source.Select(x => x.ToString());
    result.AssertSequenceEqual("1", "5", "2");
}

Secondly, I have a test that shows what sort of bizarre situations you can get into if you include side effects in your query. We could have done this with Where as well of course, but it’s clearer with Select:

[Test]
public void SideEffectsInProjection()
{
    int[] source = new int[3]; // Actual values won’t be relevant
    int count = 0;
    var query = source.Select(x => count++);
    query.AssertSequenceEqual(0, 1, 2);
    query.AssertSequenceEqual(3, 4, 5);
    count = 10;
    query.AssertSequenceEqual(10, 11, 12);
}

Notice how we’re only calling Select once, but the results of iterating over the results change each time – because the "count" variable has been captured, and is being modified within the projection. Please don’t do things like this.

Thirdly, we can now write query expressions which include both "select" and "where" clauses:

[Test]
public void WhereAndSelect()
{
    int[] source = { 1, 3, 4, 2, 8, 1 };
    var result = from x in source
                 where x < 4
                 select x * 2;
    result.AssertSequenceEqual(2, 6, 4, 2);
}

There’s nothing mind-blowing about any of this, of course – hopefully if you’ve used LINQ to Objects at all, this should all feel very comfortable and familiar.

Let’s implement it!

Surprise surprise, we go about implementing Select in much the same way as Where. Again, I simply copied the implementation file and tweaked it a little – the two methods really are that similar. In particular:

  • We’re using iterator blocks to make it easy to return sequences
  • The semantics of iterator blocks mean that we have to separate the argument validation from the real work. (Since I wrote the previous post, I’ve learned that VB11 will have anonymous iterators, which will avoid this problem. Sigh. It just feels wrong to envy VB users, but I’ll learn to live with it.)
  • We’re using foreach within the iterator blocks to make sure that we dispose of the input sequence iterator appropriately – so long as our output sequence iterator is disposed or we run out of input elements, of course.

I’ll skip straight to the code, as it’s all so similar to Where. It’s also not worth showing you the version with an index – because it’s such a trivial difference.

public static IEnumerable<TResult> Select<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, TResult> selector)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }
    if (selector == null)
    {
        throw new ArgumentNullException("selector");
    }
    return SelectImpl(source, selector);
}

private static IEnumerable<TResult> SelectImpl<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, TResult> selector)
{
    foreach (TSource item in source)
    {
        yield return selector(item);
    }
}

Simple, isn’t it? Again, the real "work" method is even shorter than the argument validation.

Conclusion

While I don’t generally like boring my readers (which may come as a surprise to some of you) this was a pretty humdrum post, I’ll admit. I’ve emphasized "just like Where" several times to the point of tedium very deliberately though – because it makes it abundantly clear that there aren’t really as many tricky bits to understand as you might expect.

Something slightly different next time (which I hope will be in the next few days). I’m not quite sure what yet, but there’s an awful lot of methods still to choose from…

General, Wacky Ideas

A Model/View to a Kill (Naked came the null delegate, part 5)

5 Comments

(I suggest you read the earlier parts of the story first. I’m not claiming it’ll make any more sense afterwards, mind you.)

Even though Seymour Sharpton’s brain was in a spinlock, a low-level interrupt brought him out of his stupor – namely, an enormous motorcycle bursting through the floor near the daemon. It was impossible to tell the form of the rider under the leather and helmet. When the biker spoke, the voice was digitally disguised but its authority was clear:

"Sharpton. Here, now. The rest of you: you know me. Follow us, and there’ll be trouble."

Algol hissed sharply, and then started cajoling Seymour: "Don’t go. Stay with us. My master didn’t mean what he said about, um, deletion. It was just a little joke. You’re safe here…"

But Seymour was already running towards the motorcycle. The biker had never stopped revving the engine, and the moment Seymour jumped on the rear seat, the wheels span briefly, kicking up clouds of dust before the bike raced through the warehouse and through the (fortunately still open) door.

The ride was fast, bumpy, and terrifying. Seymour hadn’t felt like this since he’d given up C, years ago. The roar of the engine drowned out any conversation, and he was left holding on for dear life until the bike came to a screeching halt in a deserted street. The biker dismounted and offered a hand to Seymour, who shook it nervously.

"Who are you?" he murmured, almost afraid to find out.

"My name is unimportant," replied the metallic voice, still masked by the helmet.

"It’s not Slartibartfast, is it?" Seymour had visions of being whisked away to see fjords. That would just about fit in with the rest of his strange evening.

"No, it’s… unspeakable."

"Ah, so you’re an anonymous type of guy, huh?"

"Anonymous, yes… guy, no." The biker removed her helmet and shook her head. Her long blonde hair swooshed from side to side, and time seemed to slow for Seymour as he watched her. She was a model he could view forever… although the idea of trying to control her seemed out of the question. Then several strands of hair were caught in the anonymous girl’s gently pouting mouth, and she spat them out hurriedly. "Damn it, I hate it when that happens. Anyway, you are lucky to be alive. You have no idea what our shady underworld contains… those zombies aren’t the worst of it by a long chalk."

"There’s more?" Seymour gulped.

"Worse than you can imagine. We’re lucky it’s a new moon tonight, for example. Otherwise this place would be heaving with were-clauses. Most of the month they just filter as normal, but come the full moon… urgh." She shuddered, and Seymour didn’t want to ask any further. The biker paused, and then continued.

"Then there’s the mutants. They’re harmless enough, but not for want of trying. They’ll lope after you, but they mutate almost without thinking about it. Totally dysfunctional. A quick kick to the monads will usually despatch them… But tonight, we have something else to fear." She looked around, cautiously. "The word on the street is that the Vimpires are in town. Every few years we think we’ve got rid of them… and then they come back, with their long and surprisingly dexterous fingers. You know how you can tell when the Vimpires are around?"

Seymour was spellbound. "How?"

"The mice all leave, in droves. The rats don’t care, but a Vimpires will torture a mouse just for the fun of it. But this time, there are rumours. There’s talk of a bigger plan afoot. The one thing the Vimpires are still afraid of is bright light. During the day, we’re safe… but imagine if there were no more days? Perpetual twilight – like "Breaking Dawn part 1" but forever."

"They wouldn’t!" Seymour gasped. He remembered that long night in the cinema only too well.

"They would. And they have allies… for the first time, the Eclipse posse and the Vimpires are joining forces. So we have to fight them. You’re not the first innocent man I’ve rescued tonight, and you won’t be the last. But I need to be sure of you… do you have references?"

"Um, what kind of references?"

"Anything to prove your identity. It’s a class war out there, Seymour… now what type of man are you? Where do your values lie? Oh, never mind… I’ll trust you for now. But Seymour, you need to be ready. Brace yourself. Are you in The Zone?"

"I don’t know what you mean… what zone are you talking about?"

"Ah, true, that was ambiguous. UTC or not UTC, that is the question. Whether ’tis nobler in in the mind to suffer the leap seconds and missing hours of outrageous chronology, or to take ARM against a sea of doubles, and by opposing end them?"

"What on earth are you babbling about?"

"No matter. All you need to know is this… the Vimpires are trying to extinguish the sun, but we’re going to stop them. It’s daylight saving time."

Continued in part 6 – The Great Destructor…

C#, General

Creative freedom, control, and the balance of power

12 Comments

Stephen Colebourne’s comment on my last blog post (adding 1 month -1 day to January 29th) have knocked me for six. To avoid thinking about how I might implement the preferred behaviour in Noda Time while still using Joda Time’s "engine" I’ve decided to write about something else which has been niggling at me.

For a long time, I’ve espoused the idea of "design for inheritance or prohibit it" – in other words, default to sealing classes and making methods non-virtual unless you have a good reason to do otherwise. I’ve usually attributed this phrase to Josh Bloch writing in Effective Java, but it could well have been round for a long time.

Whenever I’ve espoused this in public, it’s caused disagreement. Not universal disagreement (which would be easy to cope with; if everyone else thinks I’m wrong, that’s a very strong indicator that I’m really missing something) but a fairly even distribution of "absolutely" and "hell no". Most people seem to feel passionately one way or the other. This has led me to water down my line of "the C# designers should have made classes sealed by default" to "the C# designers shouldn’t have included a default for classes being sealed or not – make the developer specify it".

One thing I’ve found interesting is that the split between "make everything non-virtual" and "make everything virtual" isn’t one of "smart" vs "dumb". There are plenty of publically admired developers on both sides of the fence, and my colleagues are reasonably evenly split too. However, I have detected a correlation in terms of programming preferences around type systems: I’ve generally found that those who are in favour of making everything virtual by default are generally more likely to also be enthusiastic around dynamic typing. That won’t be universally true of course, but I think one is likely to be a reasonably good predictor of the other.

Ultimately I think it’s about a balance, and different people place different amounts of value on the various pros and cons. It’s also about the relationship between different parties. Different pros and cons affect different parties in different ways.

A relatively inflexible API with a flexible implementation

I’m happy when I know everything that is going on in my code. I interact with other code through obvious dependencies: they are provided to me explicitly. You’re welcome to modify my code’s visible behaviour by implementing those dependencies in different ways, but my code should be fine as long as you abide by the contracts expressed in the dependencies (typically interfaces).

If I call one of my own non-virtual methods from within my code, I know what it’s going to do. If I have two non-virtual methods which could be implemented by one calling the other either way round, then it doesn’t matter which option I pick. I can change my mind later on, and no-one will be any the wiser. All the externally visible behaviour will be exactly the same. I don’t need to document which method calls which – just what the final results are.

If I create an immutable type and seal it, then all the immutability is within my control. If I’ve picked immutable types for my member variables, have Object as a base class, and make sure I don’t mutate anything myself, I’m fine. I can rely on my values being unchanging, and so can my callers. They can cache a value with impunity.

Basically, everything is simple… unless you want to make one of my types behave slightly differently.

Flexibility with the risk of breakage

The above section sounds all nice and rosy… but what if you want to just tweak my type slightly? You only want to override one method – how much harm can that do? You’ve looked at the implementation and seen that nothing actually relies on it working exactly the way it does… and it doesn’t call any other public members. If my type implements an interface including the member you want to tweak, then you could potentially implement the interface and delegate almost all calls to an instance of the original type, but implement that one call differently. Of course, delegation is great in many cases – but can fail when there are complex relationships involved (such as when the delegated instance passes itself to something else). Basically there are identity issues.

It would be much simpler in this case if you could override my method. That might help your testing, or allow you to use my type in a way I’d never anticipated, achieving fabulous things. As Stroustrup wrote, "I wouldn’t like to build a tool that could only do what I had been able to imagine for it." Now I believe there’s a big difference between imagining a "big picture" which my component may be some tiny part of, and imagining a crazy use for the type itself, but the sentiment is still worth considering. Creative freedom is a nice thing to have, after all… who am I to stop you from achieving greatness?

The downside is that you’re opening yourself to the risk of your code breaking if I change my implementation details in another release. Maybe it would only mean your tests breaking – maybe it’s your production code. (While I don’t want to put too many words in the mouths of those who hold the opposite opinion to me, I believe a lot of their reason for wanting to be able to override methods is to make testing easier. Personally I prefer to construct test doubles which implement interfaces directly, but I do understand that’s not always feasible – especially if the component in question hasn’t been designed with testability in mind to start with.)

In many cases there’s genuinely little risk of that actually happening… but how tolerant are you of that risk?

Risk evaluation and propagation

When I wrote about what might break if the library producer changes their code, I mentioned your production code and your test code. There’s a much nastier risk though: you break someone else’s code which is relying on yours.

Suppose I produce library X, and you use it in library Y. Now Joe Developer uses both of our libraries in his application… except he uses a new version of X. Maybe it’s a bug-fix version, which is meant to have no externally-visible changes… except it changes how it uses its own methods, in a way which will break if you’ve overridden some methods in a particular way… and you’ve done so in library Y. As far as Joe Developer is concerned, his combination of X + Y is broken. Who’s fault is it?

  • Mine for changing the behaviour of X in a seemingly sensible way?
  • Yours for overriding a member of X in Y in a way I hadn’t anticipated?
  • Joe’s for using a version of X which you hadn’t developed Y against?

Maybe all three. The trouble is, as the developer of Y you have no way of knowing how likely it is that I’ll change the details of my implementation in "seemingly harmless" ways. Indeed, you may even have performed some testing of Y against the version of X that Joe is using… but maybe Joe’s overriding some other members of the types from X and Y in ways that neither you nor I expected… and the combination could be complex to work out.

Now this all sounds like doom and gloom – but you need to remember that there must have been reasons for overriding those members to start with. Achieving the same goals without using inheritance could certainly have been considerably more complex, and introduced other bugs along the way. Using inheritance could have been a big win all round, right up until the point where everything screwed up… at which point it may still be recoverable, or it could be a knot which can’t be untied. You probably won’t know until the breakage happens, and you probably can’t accurately gauge the likelihood of it happening in the first place. It may well never happen.

Three options as library providers and consumers

It seems to me that when you’re building an API, there are three broad options available (obviously with nuanced positions between them):

  • Make every type unsealed, and every method virtual – but don’t make any guarantees about what will happen if someone overrides methods.
  • Make every type unsealed and every method virtual – but document/guarantee every internal interaction, so that anyone deriving from your class can predict how it will behave.
  • Make everything sealed or non-virtual unless you can foresee a reason for overriding it. Document what sort of overriding you expect to handle, and where the overridden methods will be called.

As the consumer of an API, you have various choices too:

  • Rely on undocumented behaviour, betting that you’ll save more time by doing and fixing breakage later
  • Only rely on documented behaviour when calling code, but rely on undocumented behaviour when overriding code, as this is typically less well documented anyway (very few APIs will specify exactly what’s deemed acceptable)
  • Only rely on documented behaviour

While these options are reasonably easy to describe, they again miss the oh-so-common situation: I’m consuming someone else’s types, but providing my own types to other developers. This mixed behaviour is where a lot of the complexity comes in, increasing the risk of breakage and increasing the cost of fixing the problem.

Conclusion

I still believe that designing for inheritance or prohibiting it makes sense if you want to provide a robust library which makes it hard for the consumer to abuse. However, I appreciate that others want the ability to abuse a library – and are willing to pay the price for that down the line. I’m concerned by the "3 party" scenario though – where developer X can shoot your foot off by abusing my code.

Sadly, I can’t see this long-running argument coming any closer to resolution. Better mix-in support within C# would at least help, I believe – but delegation is no panacea either.

I want to be a pragmatic developer: I dislike the dogmatic prohibition of convenient practices for the sake of purely theoretical reasons as much as the next person… and I genuinely can see where it can be a pain not being able to override behaviour at times. However, I have yet to be convinced that a gung-ho, "It probably won’t break, honest!" attitude is really a good option in the long term. I hope I’m gaining an increasingly open mind though – and I hope that at least by discussing this from slightly less religious viewpoints from normal, both camps can learn something from each other.

Noda Time

The joys of date/time arithmetic

28 Comments

(Cross-posted to my main blog and the Noda Time blog, in the hope that the overall topic is still of interest to those who aren’t terribly interested in Noda Time per se.)

I’ve been looking at the "period" part of Noda Time recently, trying to redesign the API to simplify it somewhat. This part of the API is what we use to answer questions such as:

  • What will the date be in 14 days?
  • How many hours are there between now and my next birthday?
  • How many years, months and days have I been alive for?

I’ve been taking a while to get round to this because there are some tricky choices to make. Date and time arithmetic is non-trivial – not because of complicated rules which you may be unaware of, but simply because of the way calendaring systems work. As ever, time zones make life harder too. This post won’t talk very much about the Noda Time API details, but will give the results of various operations as I currently expect to implement them.

The simple case: arithmetic on the instant time line

One of the key concepts to understand when working with time is that the usual human "view" on time isn’t the only possible one. We don’t have to break time up into months, days, hours and so on. It’s entirely reasonable (in many cases, at least) to consider time as just a number which progresses linearly. In the case of Noda Time, it’s the number of ticks (there are 10 ticks in a microsecond, 10,000 ticks in a millisecond, and 10 million ticks in a second) since midnight on January 1st 1970 UTC.

Leaving relativity aside, everyone around the world can agree on an instant, even if they disagree about everything else. If you’re talking over the phone (using a magic zero-latency connection) you may think you’re in different years, using different calendar systems, in different time zones – but still both think of "now" as "634266985845407773 ticks".

That makes arithmetic really easy – but also very limited. You can only add or subtract numbers of ticks, effectively. Of course you can derive those ticks from some larger units which have a fixed duration – for example, you could convert "3 hours" into ticks – but some other concepts don’t really apply. How would you add a month? The instant time line has no concept of months, and in most calendars different months have different durations (28-31 days in the ISO calendar, for example). Even the idea of a day is somewhat dubious – it’s convenient to treat a day as 24 hours, but you need to at least be aware that when you translate an instant into a calendar that a real person would use, days don’t always last for 24 hours due to daylight savings.

Anyway, the basic message is that it’s easy to do arithmetic like this. In Noda Time we have the Instant structure for the position on the time line, and the Duration structure as a number of ticks which can be added to an Instant. This is the most appropriate pair of concepts to use to measure how much time has passed, without worrying about daylight savings and so on: ideal for things like timeouts, cache purging and so on.

Things start to get messy: local dates, times and date/times

The second type of arithmetic is what humans tend to actually think in. We talk about having a meeting in a month’s time, or how many days it is until Christmas (certainly my boys do, anyway). We don’t tend to consciously bring time zones into the equation – which is a good job, as we’ll see later.

Now just to make things clear, I’m not planning on talking about recurrent events – things like "the second Tuesday and the last Wednesday of every month". I’m not planning on supporting recurrences in Noda Time, and having worked on the calendar part of Google Mobile Sync for quite a while, I can tell you that they’re not fun. But even without recurrences, life is tricky.

Introducing periods and period arithmetic

The problem is that our units are inconsistent. I mentioned before that "a month" is an ambiguous length of time… but it doesn’t just change by the month, but potentially by the year as well: February is either 28 or 29 days long depending on the year. (I’m only considering the ISO calendar for the moment; that gives enough challenges to start with.)

If we have inconsistent units, we need to keep track of those units during arithmetic, and even request that the arithmetic be performed using specific units. So, it doesn’t really make sense to ask "how long is the period between June 10th 2010 and October 13th 2010" but it does make sense to ask "how many days are there between June 10th 2010 and October 13th 2010" or "how many years, months and days are there between June 10th 2010 and October 13th 2010".

Once you’ve got a period – which I’ll describe as a collection of unit/value pairs, e.g. "0 years, 4 months and 3 days" (for the last example above) you can still give unexpected behaviour. If you add that period to your original start date, you should get the original end date… but if you advance the start date by one day, you may not advance the end date by one day. It depends on how you handle things like "one month after January 30th 2010" – some valid options are:

  • Round down to the end of the month: February 28th
  • Round up to the start of the next month: March 1st
  • Work out how far we’ve overshot, and apply that to the next month: March 2nd
  • Throw an exception

All of these are justifiable. Currently, Noda Time will always take the first approach. I believe that JSR-310 (the successor to Joda Time) will allow the behaviour to be resolved according to a strategy provided by the user… it’s unclear to me at the moment whether we’ll want to go that far in Noda Time.

Arithmetic in Noda Time is easily described, but the consequences can be subtle. When adding or subtracting a period from something like a LocalDate, we simply iterate over all of the field/value pairs in the period, starting with the most significant, and add each one in turn. When finding the difference between two LocalDate values with a given set of field types (e.g. "months and days") we get as close as we can without overshooting using the most significant field, then the next field etc.

The "without overshooting" part means that if you add the result to the original start value, the result will always either be the target end value (if sufficiently fine-grained fields are available) or somewhere between the original start and the target end value. So "June 2nd 2010 to October 1st 2010 in months" gives a result of "3 months" even though if we chose "4 months" we’d only overshoot by a tiny amount.

Now we know what approach we’re taking, let’s look at some consequences.

Asymmetry and other oddities

It’s trivial to show some assymetry just using a period of a single month. For example:

  • January 28th 2010 + 1 month = February 28th 2010
  • January 29th 2010 + 1 month = February 28th 2010
  • January 30th 2010 + 1 month = February 28th 2010
  • February 28th 2010 – 1 month = January 28th 2010

It gets even more confusing when we add days into the mix:

  • January 28th 2010 + 1 month + 1 day = March 1st 2010
  • January 29th 2010 + 1 month + 1 day = March 1st 2010
  • March 1st 2010 – 1 month – 1 day = January 31st 2010

And leap years:

  • March 30th 2013 – 1 year – 1 month – 10 days = February 19th 2012 (as "February 30th 2012" is truncated to February 29th 2012)
  • March 30th 2012 – 1 year – 1 month – 10 days = February 18th 2012 (as "February 30th 2011" is truncated to February 28th 2011)

Then we need to consider how rounding works when finding the difference between days… (forgive the pseudocode):

  • Between(January 31st 2010, February 28th 2010, Months & Days) = ?
  • Between(February 28th 2010, January 31st 2010, Months & Days) = -28 days

The latter case is relatively obvious – because if you take a whole month of February 28th 2010 you end up with January 28th 2010, which is an overshoot… but what about the first case?

Should we return the determine the number of months by "the largest number such that start + period <= end"? If so, we get a result of "1 month" – which makes sense given the first set of results in this section.

What worries me most about this situation is that I honestly don’t know offhand what the current implementation will do. I think it would be best to return "28 days" as there isn’t genuinely a complete month between the two… <tappety tappety>

Since writing the previous paragraph, I’ve tested it, and it returns 1 month and 0 days. I don’t know how hard it would be to change this behaviour or whether we want to. Whatever we do, however, we need to document it.

That’s really at the heart of this: we must make Noda Time predictable. Where there are multiple feasible results, there should be a simple way of doing the arithmetic by hand and getting the same results as Noda Time. Of course, picking the best option out of the ones available would be good – but I’d rather be consistent and predictable than "usually right" be unpredictably so.

Think it’s bad so far? It gets worse…

ZonedDateTime: send in the time zones… (well maybe next year?)

I’ve described the "instant time line" and its simplicity.

I’ve described the local date/time complexities, where there’s a calendar but there’s no time zone.

So far, the two worlds have been separate: you can’t add a Duration to a LocalDateTime (etc), and you can’t add a Period to an Instant. Unfortunately, sooner or later many applications will need ZonedDateTime.

Now, you can think of ZonedDateTime in two different ways:

  • It’s an Instant which knows about a calendar and a time zone
  • It’s a LocalDateTime which knows about a time zone and the offset from UTC

The "offset from UTC" part sounds redundant at first – but during daylight saving transitions the same LocalDateTime occurs at two different instants; the time zone is the same in both cases, but the offset is different.

The latter way of thinking is how we actually represent a ZonedDateTime internally, but it’s important to know that a ZonedDateTime still unambiguously maps to an Instant.

So, what should we be able to do with a ZonedDateTime in terms of arithmetic? I think the answer is that we should be able to add both Periods and Durations to a ZonedDateTime – but expect them to give different results.

When we add a Duration, that should work out the Instant represented by the current DateTime, advance it by the given duration, and return a new ZonedDateTime based on that result with the same calendar and time zone. In other words, this is saying, "If I were to wait for the given duration, what date/time would I see afterwards?"

When we add a Period, that should add it to the LocalDateTime represented by the ZonedDateTime, and then return a new ZonedDateTime with the result, the original time zone and calendar, and whatever offset is suitable for the new LocalDateTime. (That’s deliberately woolly – I’ll come back to it.) This is the sort of arithmetic a real person would probably perform if you asked them to tell you what time it would be "three hours from now". Most people don’t take time zones into account…

In most cases, where a period can be represented as a duration (for example "three hours") the two forms of addition will give the same result. Around daylight saving transitions, however, they won’t. Let’s consider some calculations on Sunday November 7th 2010 in the "Pacific/Los_Angeles" time zone. It had a daylight saving transition from UTC-7 to UTC-8 at 2am local time. In other words, the clock went 1:58, 1:59, 1:00. Let’s start at 12:30am (local time, offset = -7) and add a few different values:

  • 12:30am + 1 hour duration = 1:30am, offset = -7
  • 12:30am + 2 hours duration = 1:30am, offset = -8
  • 12:30am + 3 hours duration = 2:30am, offset = -8
  • 12:30am + 1 hour period = 1:30am, offset = ???
  • 12:30am + 2 hour period = 2:30am, offset = -8
  • 12:30am + 3 hour period = 3:30am, offset = -8

The ??? value is the most problematic one, because 1:30 occurs twice… when thinking of the time in a calendar-centric way, what should the result be? Options here:

  • Always use the earlier offset
  • Always use the later offset
  • Use the same offset as the start date/time
  • Use the offset in the direction of travel (so adding one hour from 12:30am would give 1:30am with an offset of -7, but subtracting one hour from 2:30am would give 1:30am with an offset of -8)
  • Throw an exception
  • Allow the user to pass in an argument which represents a strategy for resolving this

This is currently unimplemented in Noda Time, so I could probably choose whatever behaviour I want, but frankly none of them has much appeal.

At the other daylight saving transition, when the clocks go forward, we have the opposite problem: adding one hour to 12:30am can’t give 1:30am because that time never occurs. Options in this case include:

  • Return the first valid time after the transition (this has problems if we’re subtracting time, where we’d presumably want to return the latest valid time before the transition… but the transition has an exclusive lower bound, so there’s no such "latest valid time" really)
  • Add the offset difference, so we’d skip to 2:30am
  • Throw an exception
  • Allow the user to pass in a strategy

Again, nothing particularly appeals.

All of this is just involved in adding a period to a ZonedDateTime – then the same problems occur all over again when trying to find the period between them. What’s the difference (as a Period rather than a simple Duration) between 1:30am with an offset of -7 and 1:30am with an offset of -8? Nothing, or an hour? Again, at the moment I really don’t know the best course of action.

Conclusion

This post has ended up being longer than I’d expected, but hopefully you’ve got a flavour of the challenges we’re facing. Even without time zones getting involved, date and time arithmetic is pretty silly – and with time zones, it becomes very hard to reason about – and to work out what the "right" result to be returned by an API should be, let alone implement it.

Above all, it’s important to me that Noda Time is predictable and clearly documented. Very often, if a library doesn’t behave exactly the way you want it to, but you can tell what it’s going to do, you can work around that – but if you’re having to experiment to guess the behaviour, you’re on a hiding to nothing.

async, C#, C# 5

The importance of context, and a question of explicitness

14 Comments

(Just to be clear: I hate the word "explicitness". It reminds me of Rowan Atkinson as Marcus Browning MP, saying we should be purposelessnessless. But I can’t think of anything better here.)

For the last few days, I’ve been thinking about context – in the context of C# 5’s proposed asynchronous functionality. Now many of the examples which have been presented have been around user interfaces, with the natural restriction of doing all UI operations on the UI thread. While that’s all very well, I’m more interested in server-side programming, which has a slightly different set of restrictions and emphases.

Back in my post about configuring waiting, I talked about the context of where execution would take place – both for tasks which require their own thread and for the continuations. However, thinking about it further, I suspect we could do with richer context.

What might be included in a context?

We’re already used to the idea of using context, but we’re not always aware of it. When trying to service a request on a server, some or any of the following may be part of our context:

  • Authentication information: who are we acting as? (This may not be the end user, of course. It may be another service who we trust in some way.)
  • Cultural information: how should text destined for an end user by rendered? What other regional information is relevant?
  • Threading information: as mentioned before, what threads should be used both for "extra" tasks and continuations? Are we dealing with thread affinity?
  • Deadlines and cancellation: the overall operation we’re trying to service may have a deadline, and operations we create may have their own deadlines too. Cancellation tokens in TPL can perform this role for us pretty easily.
  • Logging information: if the logs need to tie everything together, there may be some ID generated which should be propagated.
  • Other request information: very much dependent on what you’re doing, of course…

We’re used to some of this being available via properties such as CultureInfo.CurrentCulture and HttpContext.Current – but those are tied to a particular thread. Will they be propagated to threads used for new tasks or continuations? Historically I’ve found that documentation has been very poor around this area. It can be very difficult to work out what’s going to happen, even if you’re aware that there’s a potential problem in the first place.

Explicit or implicit?

It’s worth considering what the above items have in common. Why did I include those particular pieces of information but not others? How can we avoid treating them as ambient context in the first place?

Well, fairly obviously we can pass all the information we need along via method arguments. C# 5’s async feature actually makes this easier than it was before (and much easier that it would have been without anonymous functions) because the control flow is simpler. There should be fewer method calls, each of which would each require decoration with all the contextual information required.

However, in my experience that becomes quite problematic in terms of separation of concerns. If you imagine the request as a tree of asynchronous operations working down from a top node (whatever code initially handles the request), each node has to provide all the information required for all the nodes within its subtree. If some piece of information is only required 5 levels down, it still needs to be handed on at each level above that.

The alternative is to use an implicit context – typically via static methods or properties which have to do the right thing, typically based on something thread-local. The context code itself (in conjunction with whatever is distributing the work between threads) is responsible for keeping track of everything.

It’s easy to point out pros and cons to both approaches:

  • Passing everything through methods makes the dependencies very obvious
  • Changes to "lower" tasks (even for seemingly innocuous reasons such as logging) end up causing chains of changes higher up the task tree – possibly to developers working on completely different projects, depending on how your components work
  • It feels like there’s a lot of work for very little benefit in passing everything explicitly through many layers of tasks
  • Implicit context can be harder to unit test elegantly – as is true of so many things using static calls
  • Implicit context requires everyone to use the same context. It’s no good high level code indicating which thread pool to use in one setting when some lower level code is going to use a different context

Ultimately it feels like a battle between purity and pragmatism: being explicit helps to keep your code purer, but it can mean a lot of fluff around your real logic, just to maintain the required information to pass onward. Different developers will have different approaches to this, but I suspect we want to at least keep the door open to both designs.

The place of Task/Task<T>

Even if Task/Task<T> can pass on the context for scheduling, what do we do about other information (authentication etc)? We have types like ThreadLocal<T> – in a world where threads are more likely to be reused, and aren’t really our unit of asynchrony, do we effectively need a TaskLocal<T>? Can context within a task be pushed and automatically popped, to allow one subtree to "override" the context for its nodes, while another subtree works with the original context?

I’ve been trying to think about whether this can be provided in "userland" code instead of in the TPL itself, but I’m not sure it can, easily… at least not without reinventing a lot of the existing code, which is never a good idea when it’s tricky parallelization code.

Should this be general support, or would it be okay to stick to just TaskScheduler.Current, leaving developers to pass other context explicitly?

Conclusion

These are thoughts which I’m hoping will be part of a bigger discussion. I think it’s something the community should think about and give feedback to Microsoft on well before C# 5 (and whatever framework it comes with) ships. I have lots of contradictory feelings about the right way to go, and I’m fully expecting comments to have mixed opinions too.

I’m sure I’ll be returning to this topic as time goes on.

Addendum (March 27th 2012)

Lucian Wischik recently mailed me about this post, to mention that F#’s support for async has had the ability to retain explicit context from the start. It’s also more flexible than the C# async support – effectively, it allows you to swap out AsyncTaskMethodBuilder etc for your own types, so you don’t always have to go via Task/Task<T>. I’ll take Lucian’s word for that, not knowing much about F# myself. One day…

async, C#, C# 5

Multiple exceptions yet again… this time with a resolution

5 Comments

I’ve had a wonderful day with Mads Torgersen, and amongst other things, we discussed multiple exceptions and the way that the default awaiter for Task<T> handles an AggregateException by taking the first exception and discarding the rest.

I now have a much clearer understanding of why this is the case, and also a workaround for the cases where you really want to avoid that truncation.

Why truncate in the first place?

(I’ll use the term "truncate" throughout this post to mean "when an AggregatedException with at least one nested exception is caught by EndAwait, throw the first nested exception instead". It’s just a shorthand.)

Yesterday’s post on multiple exceptions showed what you got if you called Wait() on a task returned from an async method. You still get an AggregateException, so why bother to truncate it?

Let’s consider a slightly different situation: where we’re awaiting an async method that throws an exception, and you want to be able to catch some specific exception that will be thrown by that asynchronous method. Imagine we used my NaiveAwaiter class. That would mean we would have to catch AggregateException, check whether one of those exceptions was actually present, and then handle that. There’d then be an open question about what to do if there were other exceptions as well… but that would be a relatively rare case. (Remember, we’re talking about multiple "top level" exceptions within the AggregateException – not just one exception nested in another, nested in another etc.)

With the current awaiter behaviour, you can catch the exception exactly as you would have done in synchronous code. Here’s an example:

using System;
using System.Threading.Tasks;
using System.Collections.Generic;

public class BangException : Exception 
{
    public BangException(string message) : base(message) {}
}

public class Test
{
    public static void Main()
    {
        FrobAsync().Wait();
    }
    
    private static async Task FrobAsync()
    {
        Task fuse = DelayedThrow(500);
        try
        {
            await fuse;
        }
        catch (BangException e)
        {
            Console.WriteLine("Caught it! ({0})", e.Message);
        }
    }
    
    static async Task DelayedThrow(int delayMillis) 
    { 
        await TaskEx.Delay(delayMillis);
        throw new BangException("Went bang after " + delayMillis + "ms");
    }
}

Nice and clean exception handling… assuming that the task we awaited asynchronously didn’t have multiple exceptions. (Note the improved DelayedThrow method, by the way. Definitely cleaner than my previous version.)

This aspect of "the async code looks like the synchronous code" is the important bit. One of the key aims of the language feature is to make it easy to write asynchronous code as if it were synchronous – because that’s what we’re used to, and what we know how to reason about. We’re fairly used to the idea of catching one exception… not so much on the "multiple things can go wrong at the same time" front.

So that handles the primary case where we really expect to only have one exception (if any) because we’re only performing one job.

What about cases where multiple exceptions are somewhat expected?

Let’s go back to the case where we really to propagate multiple exceptions. I think it’s reasonable that this should be an explicit opt-in, so let’s think about an extension method. For the sake of simplicity I’ll use Task – in real life we’d want Task<T> as well, of course. So for example, this line:

await TaskEx.WhenAll(t1, t2);

would become this:

await TaskEx.WhenAll(t1, t2).PreserveMultipleExceptions();

(Yes, the name is too long… but you get the idea.)

Now, there are two ways we could make this work:

  • We could make the extension method return something which had a GetAwaiter method, returning something which in turn had BeginAwait and EndAwait methods. This means making sure we get all of the awaiter code right, of course – and the returned value has little meaning outside an await expression.
  • We could wrap the task in another task, and use the existing awaiter code. We know that the EndAwait extension method associated with Task (and Task<T>) will go into a single level of AggregateException – but I don’t believe it will do any more than that. So if it’s going to strip one level of exception aggregation off, all we need to do is add another level.

According to Mads, the latter of these is easier. Let’s see if he’s right.

We need an extension method on Task, and we’re going to return Task too. How can we implement that?

  • We can’t await the task, because that will strip the exception before we get to it.
  • We can’t write an async task but call Wait() on the original task, because that will block immediately – we still want to be async.
  • We can use a TaskCompletionSource<T> to build a task. We don’t care about the actual result, so we’ll use TaskCompletionSource<object>. This will actually build a Task<object>, but we’ll return it as a Task anyway, and use a null result if it completes with no exception. (This was Mads’ suggestion.)

So, we know how to build a Task, and we’ve been given a Task – how do we hook the two together? The answer is to ask the original task to call us back when it completes, via the ContinueWith method. We can then set the result of our task accordingly. Without further ado, here’s the code:

public static Task PreserveMultipleExceptions(this Task originalTask)
{
    var tcs = new TaskCompletionSource<object>();
    originalTask.ContinueWith(t => {
        switch (t.Status) {
            case TaskStatus.Canceled:
                tcs.SetCanceled();
                break;
            case TaskStatus.RanToCompletion:
                tcs.SetResult(null);
                break;
            case TaskStatus.Faulted:
                tcs.SetException(originalTask.Exception);
                break;
        }
    }, TaskContinuationOptions.ExecuteSynchronously);
    return tcs.Task;
}

This was thrown together in 5 minutes (in the middle of a user group talk by Mads) so it’s probably not as robust as it might be… but the idea is that when the original task completes, we just piggy-back on the same thread very briefly to make our own task respond appropriately. Now when some code awaits our returned task, we’ll add an extra wrapper of AggregateException on top, ready to be unwrapped by the normal awaiter.

Note that the extra wrapper is actually added for us really, really easily – we just call TaskCompletionSource<T>.SetException with the original task’s AggregateException. Usually we’d call SetException with a single exception (like a BangException) and the method automatically wraps it in an AggregateException – which is exactly what we want.

So, how do we use it? Here’s a complete sample (just add the extension method above):

using System;
using System.Threading.Tasks;

public class BangException : Exception  
{ 
    public BangException(string message) : base(message) {} 
}

public class Test
{
    public static void Main()
    {
        FrobAsync().Wait();
    }
    
    public static async Task FrobAsync()
    {
        try
        {
            Task t1 = DelayedThrow(500);
            Task t2 = DelayedThrow(1000);
            Task t3 = DelayedThrow(1500);
            
            await TaskEx.WhenAll(t1, t2, t3).PreserveMultipleExceptions();
        }
        catch (AggregateException e)
        {
            Console.WriteLine("Caught {0} aggregated exceptions", e.InnerExceptions.Count);
        }
        catch (Exception e)
        {
            Console.WriteLine("Caught non-aggregated exception: {0}", e.Message);
        }
    }
    
    static async Task DelayedThrow(int delayMillis)  
    {  
        await TaskEx.Delay(delayMillis); 
        throw new BangException("Went bang after " + delayMillis + "ms"); 
    }
}

The result is what we were after:

Caught 3 aggregated exceptions

The blanket catch (Exception e) block is there so you can experiment with what happens if you remove the call to PreserveMultipleExceptions – in that case we get the original behaviour of a single BangException being caught, and the others discarded.

Conclusion

So, we now have answers to both of my big questions around multiple exceptions with async:

  • Why is the default awaiter truncating exceptions? To make asynchronous exception handling look like synchronous exception handling in the common case.
  • What can we do if that’s not the behaviour we want? Either write our own awaiter (whether that’s invoked explicitly or implicitly via "extension method overriding" as shown yesterday) or wrap the task in another one to wrap exceptions.

I’m happy again. Thanks Mads :)

Uncategorized

Using extension method resolution rules to decorate awaiters

1 Comment

This post is a mixture of three things:

  • Revision of how extension methods are resolved
  • Application of this to task awaiting in async methods
  • A rant about void not being a type

Compared with my last few posts, there’s almost nothing to do with genuine asynchronous behaviour here. It’s to do with how the language supports asynchronous behaviour, and how we can hijack that support :)

Extension methods redux

I’m sure almost all of you could recite the C# 4 spec section 7.6.5.2 off by heart, but for the few readers who can’t (Newton Microkitchen Breakfast Club, I’m looking at you) here’s a quick summary.

The compiler looks for extension methods (the ones that "pretend" to be instance methods on other types, and are declared in non-generic top-level static classes) when it comes across a method invocation expression1 and finds no applicable methods. We’ll assume we’ve got to that point.

The compiler then looks in successive contexts for extension methods. It only considers non-generic static types directly declared in namespaces (as opposed to being nested classes) but it’s the order in which the namespaces are searched which is interesting. Imagine that the compiler is looking at code in a namespace X.Y.Z. That has to be within at least one namespace declaration, and can have up three, like this:

namespace X
{
    namespace Y
    {
        namespace Z
        {
            // Code being compiled
        }
    }
}

The compiler starts with the "innermost" namespace, and works outwards to the global namespace. At each level, it first considers types within that namespace, then types within any using namespace directives within the namespace declaration. So, to give a really full example, consider this:

using UD.U0;

namespace X
{
    using UD.U1;

    namespace Y
    {
       using UD.U2;

        namespace Z
        {
            using UD.U3;

            // Code being compiled
        }
    }
}

The namespaces would be searched in this order:

  • Z
  • UD.U3
  • Y
  • UD.U2
  • X
  • UD.U1
  • "global"
  • UD.U0

Note that UD itself would not be searched. If a namespace declaration contains more than one using namespace directive, they’re considered as a set of directives – the order doesn’t matter, and all types within the referenced namespaces are considered equally.

As soon as an eligible method has been found, this brings the search to a halt – even if a "better" method might be available elsewhere. This allows us to effectively prioritise extension methods within a particular namespace by including a using namespace directive in a more deeply nested namespace declaration than the methods we want to ignore.

Async methods and extensions on Task/Task<T>

So, where am I heading with all of this? Well, I wanted to work out a way of getting the compiler to use my extension methods for Task and Task<T> instead of the ones that come in the CTP library. The GetAwaiter() methods are in a type called AsyncCtpThreadingExtensions, and they both return System.Runtime.CompilerServices.TaskAwaiter instances. You can tell this just by decompiling your own code, and see what it calls when you "await" a task.

Now, we can create our own complete awaiter methods, as shown in my previous post… but it’s potentially more useful just to be able to add diagnosis tools without changing the actual behaviour. For the sake of brevity, here are some extension methods and supporting types just for Task<T> – the full code targets the non-generic Task type as well.

using System;
using System.Runtime.CompilerServices;
using System.Threading.Tasks;

namespace JonSkeet.Diagnostics
{
    public static class DiagnosticTaskExtensions
    {
        /// <summary>
        /// Associates a task with a user-specified name before GetAwaiter is called
        /// </summary>
        public static NamedTask<T> WithName<T>(this Task<T> task, string name)
        {
            return new NamedTask<T>(task, name);
        }

        /// <summary>
        /// Gets a diagnostic awaiter for a task, based only on its ID.
        /// </summary>
        public static NamedAwaiter<T> GetAwaiter<T>(this Task<T> task)
        {
            return new NamedTask<T>(task, "[" + task.Id + "]").GetAwaiter();
        }

        public struct NamedTask<T>
        {
            private readonly Task<T> task;
            private readonly string name;

            public NamedTask(Task<T> task, string name)
            {
                this.task = task;
                this.name = name;
            }

            public NamedAwaiter<T> GetAwaiter()
            {
                Console.WriteLine("GetAwaiter called for task "{0}"", name);
                return new NamedAwaiter<T>(AsyncCtpThreadingExtensions.GetAwaiter(task), name);
            }
        }

        public struct NamedAwaiter<T>
        {
            private readonly TaskAwaiter<T> awaiter;
            private readonly string name;

            public NamedAwaiter(TaskAwaiter<T> awaiter, string name)
            {
                this.awaiter = awaiter;
                this.name = name;
            }

            public bool BeginAwait(Action continuation)
            {
                Console.WriteLine("BeginAwait called for task "{0}"…", name);
                bool ret = awaiter.BeginAwait(continuation);
                Console.WriteLine("… BeginAwait for task "{0}" returning {1}", name, ret);
                return ret;
            }

            public T EndAwait()
            {
                Console.WriteLine("EndAwait called for task "{0}"", name);
                // We could potentially report the result here
                return awaiter.EndAwait();
            }
        }
    }
}

So this lets us give a task a name for clarity (optionally), and logs when the GetAwaiter/BeginAwait/EndAwait methods get called.

The neat bit is how easy this is to use. Consider this code:

using System;
using System.Net;
using System.Threading.Tasks;

namespace Demo
{
    using JonSkeet.Diagnostics;

    class Program
    {
        static void Main(string[] args)
        {
            Task<int> task = SumPageSizes();
            Console.WriteLine("Result: {0}", task.Result);
        }

        static async Task<int> SumPageSizes()
        {
            Task<int> t1 = FetchPageSize("http://www.microsoft.com&quot;);
            Task<int> t2 = FetchPageSize("http://csharpindepth.com&quot;);

            return await t1.WithName("MS web fetch") +
                   await t2.WithName("C# in Depth web fetch");
        }

        static async Task<int> FetchPageSize(string url)
        {
            string page = await new WebClient().DownloadStringTaskAsync(url);
            return page.Length;
        }
    }
}

The JonSkeet.Diagnostics namespace effectively has higher priority when we’re looking for extension methods, so our GetAwaiter is used instead of the ones in the CTP (which we delegate to, of course).

Remove the using namespace directive for JonSkeet.Diagnostics, remove the calls to WithName, and it all compiles and runs as normal. If you don’t want to have to do anything to the code, you could put the using namespace directive within #if DEBUG / #endif and write a small extension method in the System.Threading.Tasks namespace like this:

namespace System.Threading.Tasks
{
    public static class NamedTaskExtensions
    {
        public static Task<T> WithName<T>(this Task<T> task, string name)
        {
            return task;
        }
    }
}

… and bingo, diagnostics only in debug mode. The no-op WithName method will be ignored for the higher-priority version one in debug builds, and will be harmless in a release build.

The diagnostics themselves can be quite enlightening, by the way. For example, here’s the result of the previous program:

GetAwaiter called for task "[1]"
BeginAwait called for task "[1]"…
… BeginAwait for task "[1]" returning True
GetAwaiter called for task "[2]"
BeginAwait called for task "[2]"…
… BeginAwait for task "[2]" returning True
GetAwaiter called for task "MS web fetch"
BeginAwait called for task "MS web fetch"…
… BeginAwait for task "MS web fetch" returning True
EndAwait called for task "[2]"
EndAwait called for task "[1]"
EndAwait called for task "MS web fetch"
GetAwaiter called for task "C# in Depth web fetch"
BeginAwait called for task "C# in Depth web fetch"…
… BeginAwait for task "C# in Depth web fetch" returning False
EndAwait called for task "C# in Depth web fetch"
Result: 6009

This shows us waiting to fetch both web pages, and both of those awaits being asynchronous. (Note that we launched the tasks before any diagnostics were displayed – it’s only awaiting the tasks that causes all of this to kick in.) After both of those "fetch and take the length" tasks have started, we await the result of the first one (for microsoft.com). This corresponds to task 1 – but task 2 (fetching csharpindepth.com) finishes first. When the microsoft.com page has finished fetching, the length is computed and that task completes. Now when we await the result of fetching the length of csharpindepth.com, we see that it’s already finished, and the await completes synchronously.

Obviously this was a small example, I deliberately left two tasks with just task IDs, and there could be a lot more information (such as timestamps and thread IDs, to start with) but I suspect this sort of thing could be invaluable when trying to work out what’s going on in async code.

And finally… a short rant

I’ve written all the diagnostic code twice. Not because it was wrong the first time, but because it only covered Task<T>, not Task. I couldn’t write it just on Task, because then EndAwait would have had the wrong signature… but the code was pretty much a case of "cut, paste, remove <T> everywhere".

I’ve never been terribly bothered by the void type before, and it not being a "proper" type like unit in functional programming languages. Now, I suddenly begin to see the point.

Perhaps the TPL should have introduced the Unit type before the Rx team got in there. With a single Task<T> type, I suspect there’d be significantly less code duplication in the framework (including the async CTP).

Is it enough to make me wish we didn’t have void at all? Maybe. Maybe not. Perhaps with sufficient knowledge in the CLR, there wouldn’t have to be any stack penalty for copying a "pretend" return value onto the stack every time we call a method which would currently return void. I’ll certainly be keeping an eye out for other places where it would make life easier.

Conclusion

I don’t normally advocate language tricks like the extension method "priority boost" described here. I love talking about them, but I think they’re nasty enough to avoid most of the time.

But in this case the diagnostic benefit is potentially huge! I don’t know how it would fit into the full framework – or where it would dump its diagnostics to – but I’d really like to see something like this in the final release, particularly with the ability to associate a name with a task.

Even if you don’t want to actually use this, I hope you’ve enjoyed it as an intellectual exercise and a bit of reinforcement about how GetAwait/BeginAwait/EndAwait works.

1 It has to be a method invocation on an expression, too. So if you’re writing code within an IEnumerable<T> implementation and you want to call the LINQ Count() method, you have to call this.Count() rather than just Count(), for example.