Nick Guerrera's blog

I Don't Like Arrays

MSDNArchive — Tue, 27 Jun 2006 06:36:00 GMT

The number one reason that I dislike arrays in .NET is the fact that they implement IList<T> explicitly, thereby burying useful members like IndexOf behind a cast or equally ugly calls to static methods on System.Array, and needlessly renaming the Count property to Length. As a result, it's unduly difficult to change code that operates on an array to use a more versatile collection in its place.

In fact, I don't like explicit interface implementation (EII) much at all. In my opinion, there are only two valid reasons to use EII: to hide members which unconditionally throw NotSupportedException, or to implement a poor man's return type covariance or parameter type contravariance. I consider EII harmful in all other cases. [Update: I overstated things, there are other cases where EII is acceptable, see the comments for details.]

The second reason that I dislike arrays is that they show up too often in public API, which further exacerbates their impedance mismatch with other collections. (To be fair, this isn't an issue with arrays themselves so much as how they are used in the wild.)

I pointed out to colleagues this morning that the same arguments that we provide for avoiding List<T> in public API, mainly that it's designed for performance rather than extensibility, can be applied to T[].

As a follow-up to that conversation, we decided to change one of our API which returns string[] to return Collection<string>. This saved us a truly unnecessary call to List<string>.ToArray() and allows us to further customize the API in the future, perhaps by making it lazy and more efficient in the exceedingly common case where it is used only for enumeration.

I was happy with this change until it broke one of our test cases which called String.Join on the resulting array. There's no reason why String.Join couldn't take IEnumerable<string> or at least IList<string> in place of string[], but it doesn't, and we were forced to write our own Join method to work around the problem.

One of the main arguments in favor of typing parameters as arrays is to enable the addition of the params keyword. I don't dispute the convenience of params, but there's a way to have your cake and eat it too:

    public void DoSomething(params string[] arguments) {
        DoSomething((IEnumerable<string>)arguments);
    }

    public void DoSomething(IEnumerable<string> collection) {
        ...
    }

In fact, it would be nice if C# supported params IEnumerable<T> and implemented it as above, or even better would be to save the unnecessary overloads by training our compilers to make sense of ParamArrayAttribute for all trailing parameter types to which there exists an implicit conversion from the strongest array type that can hold the trailing arguments.

This actually brings me to another topic which gets a lot of press these days: dynamic vs. static typing. I've recently rekindled a fondness that I developed in university for the Scheme programming language and I've also been familiarizing myself with Ruby, which I like a lot. The most important thing that I've learned from Ruby (which might be obvious to the Smalltalkers of the world, but was news to a Java-educated punk like me), is that static typing can actually get in the way of polymorphism and object-orientation. For example, imagine if String.Join didn't declare the type of its array argument, but instead just used the features that it needed. I could then pass it a collection which happens to quack just like the array that the developer had in mind and everything would just work...

That's not to say that there's no value in static-typing. For one thing, it can help produce faster code. For another, it helps drive statement completion features like IntelliSense. And finallly, it makes my day job writing static code analysis much easier. :)

Let me summarize my thoughts as follows:

If we ever build a new framework, let's make sure that arrays and collections are syntax-compatible from day one.
Don't abuse explicit interface implementation.
Where possible, prefer abstractions like IEnumerable<T> and IList<T> over T[] for parameter types in public API.

I smell some new FxCop rules lurking. What do you think?

Exceptions, exceptions, exceptions....

MSDNArchive — Sun, 18 Jun 2006 08:24:00 GMT

I've made my first contributions to the FxCop team blog on a subject that's near and dear to my heart and often controversial: the perils of catch (Exception). Take a look here and here.

Update: The saga continues...

Opening the Coding Style Can of Worms

MSDNArchive — Thu, 15 Jun 2006 07:29:00 GMT

I find it troubling when different portions of code from the same project use different indentation and bracing styles. In my opinion, it's much easier to read and maintain code that's uniform in style. However, you won't find me arguing that any one style is objectively better than any other. Although I have my own preferences, I've found that my brain and fingers are willing to adapt to any style over time. All that they ask in return is that I try to stick with a single style while working on a single problem.

Unfortunately, our team doesn't have formal coding conventions and our code base has evolved a fair amount of inconsistency over time. I recently asked the team if we could settle on a standard indentation and bracing scheme in the future, but I now regret that I brought it up...

It's very hard to extract the benefit of reaching a consensus on this issue without wasting an inordinate number of cycles arguing about it. At the end of the day, I think I'd rather not discuss it anymore.

I'm reminded of Ken Arnold's article on the subject. Although his proposal is quite radical, it addresses all of my concerns. If we adopted his approach, we'd have 100% consistent code without spending any time arguing about it!

Presenting WeakDictionary[TKey, TValue]

MSDNArchive — Mon, 05 Jun 2006 03:14:00 GMT

This morning, I posted a base class to assist with implementing IDictionary<TKey,TValue>. As I mentioned this was just the first chunk of work required as part of my goal of building a generic dictionary which uses weak references for its keys and values.

While it's reasonably easy to use WeakReference as the TValue in Dictionary<TKey, TValue> using WeakReference as TKey is actually very tricky to get right. I've aimed to hide the heavy lifting behind the WeakDictionary abstraction so that it can be used as any other IDictionary<TKey,TValue> with the caveat that entries will disappear if either the key or value can be reclaimed by the GC. This means that you don't ever have to work directly with weak references and you can just map keys to values and the dictionary will use weak references internally to ensure that both can still be collected.

The dictionary implementation depends on a few interesting helper classes. Let's look at them first:

// Adds strong typing to WeakReference.Target using generics. Also,
// the Create factory method is used in place of a constructor
// to handle the case where target is null, but we want the 
// reference to still appear to be alive.
internal class WeakReference<T> : WeakReference where T : class {
    public static WeakReference<T> Create(T target) {
        if (target == null)
            return WeakNullReference<T>.Singleton;

        return new WeakReference<T>(target);
    }

    protected WeakReference(T target)
        : base(target, false) { }

    public new T Target {
        get { return (T)base.Target; }
    }
}

// Provides a weak reference to a null target object, which, unlike
// other weak references, is always considered to be alive. This 
// facilitates handling null dictionary values, which are perfectly
// legal.
internal class WeakNullReference<T> : WeakReference<T> where T : class {
    public static readonly WeakNullReference<T> Singleton = new WeakNullReference<T>();
    
    private WeakNullReference() : base(null) { }
    
    public override bool IsAlive {
        get { return true; }
    }
}

// Provides a weak reference to an object of the given type to be used in
// a WeakDictionary along with the given comparer.
internal sealed class WeakKeyReference<T> : WeakReference<T> where T : class {
    public readonly int HashCode;
    
    public WeakKeyReference(T key, WeakKeyComparer<T> comparer)
        : base(key) {
        // retain the object's hash code immediately so that even
        // if the target is GC'ed we will be able to find and
        // remove the dead weak reference.
        this.HashCode = comparer.GetHashCode(key);
    }
}

// Compares objects of the given type or WeakKeyReferences to them
// for equality based on the given comparer. Note that we can only
// implement IEqualityComparer<T> for T = object as there is no 
// other common base between T and WeakKeyReference<T>. We need a
// single comparer to handle both types because we don't want to
// allocate a new weak reference for every lookup.
internal sealed class WeakKeyComparer<T> : IEqualityComparer<object>
    where T : class {

    private IEqualityComparer<T> comparer;

    internal WeakKeyComparer(IEqualityComparer<T> comparer) {
        if (comparer == null)
            comparer = EqualityComparer<T>.Default;

        this.comparer = comparer;
    }

    public int GetHashCode(object obj) {
        WeakKeyReference<T> weakKey = obj as WeakKeyReference<T>;
        if (weakKey != null) return weakKey.HashCode;
        return this.comparer.GetHashCode((T)obj);
    }

    // Note: There are actually 9 cases to handle here.
    //
    //  Let Wa = Alive Weak Reference
    //  Let Wd = Dead Weak Reference
    //  Let S  = Strong Reference
    //  
    //  x  | y  | Equals(x,y)
    // -------------------------------------------------
    //  Wa | Wa | comparer.Equals(x.Target, y.Target) 
    //  Wa | Wd | false
    //  Wa | S  | comparer.Equals(x.Target, y)
    //  Wd | Wa | false
    //  Wd | Wd | x == y
    //  Wd | S  | false
    //  S  | Wa | comparer.Equals(x, y.Target)
    //  S  | Wd | false
    //  S  | S  | comparer.Equals(x, y)
    // -------------------------------------------------
    public new bool Equals(object x, object y) {
        bool xIsDead, yIsDead;
        T first  = GetTarget(x, out xIsDead);
        T second = GetTarget(y, out yIsDead);

        if (xIsDead)
            return yIsDead ? x == y : false;

        if (yIsDead)
            return false;
        
        return this.comparer.Equals(first, second);
    }

    private static T GetTarget(object obj, out bool isDead) {
        WeakKeyReference<T> wref = obj as WeakKeyReference<T>;
        T target;
        if (wref != null) {
            target = wref.Target;
            isDead = !wref.IsAlive;
        }
        else {
            target = (T)obj;
            isDead = false;
        }
        return target;
    }
} 

Getting the comparer right is actually the hardest problem to solve. Once it's out of the way, the rest is just plumbing. Here's the code for the dictionary itself:

[Update: I renamed SetEntry to SetValue for symmetry with TryGetValue.]

/// <summary>
/// A generic dictionary, which allows both its keys and values 
/// to be garbage collected if there are no other references
/// to them than from the dictionary itself.
/// </summary>
/// 
/// <remarks>
/// If either the key or value of a particular entry in the dictionary
/// has been collected, then both the key and value become effectively
/// unreachable. However, left-over WeakReference objects for the key
/// and value will physically remain in the dictionary until
/// RemoveCollectedEntries is called. This will lead to a discrepancy
/// between the Count property and the number of iterations required
/// to visit all of the elements of the dictionary using its
/// enumerator or those of the Keys and Values collections. Similarly,
/// CopyTo will copy fewer than Count elements in this situation.
/// </remarks>
public sealed class WeakDictionary<TKey, TValue> : BaseDictionary<TKey, TValue>
    where TKey : class
    where TValue : class {

    private Dictionary<object, WeakReference<TValue>> dictionary;
    private WeakKeyComparer<TKey> comparer;

    public WeakDictionary()
        : this(0, null) { }

    public WeakDictionary(int capacity)
        : this(capacity, null) { }

    public WeakDictionary(IEqualityComparer<TKey> comparer)
        : this(0, comparer) { }

    public WeakDictionary(int capacity, IEqualityComparer<TKey> comparer) {
        this.comparer = new WeakKeyComparer<TKey>(comparer);
        this.dictionary = new Dictionary<object, WeakReference<TValue>>(capacity, this.comparer);
    }

    // WARNING: The count returned here may include entries for which
    // either the key or value objects have already been garbage
    // collected. Call RemoveCollectedEntries to weed out collected
    // entries and update the count accordingly.
    public override int Count {
        get { return this.dictionary.Count; }
    }

    public override void Add(TKey key, TValue value) {

        if (key == null) throw new ArgumentNullException("key"); 
        WeakReference<TKey> weakKey = new WeakKeyReference<TKey>(key, this.comparer);
        WeakReference<TValue> weakValue = WeakReference<TValue>.Create(value);
        this.dictionary.Add(weakKey, weakValue);
    }

    public override bool ContainsKey(TKey key) {
        return this.dictionary.ContainsKey(key);
    }

    public override bool Remove(TKey key) {
        return this.dictionary.Remove(key);
    }

    public override bool TryGetValue(TKey key, out TValue value) {
        WeakReference<TValue> weakValue;
        if (this.dictionary.TryGetValue(key, out weakValue)) {
            value = weakValue.Target;
            return weakValue.IsAlive;
        }
        value = null;
        return false;
    }

    protected override void SetValue(TKey key, TValue value) {
        WeakReference<TKey> weakKey = new WeakKeyReference<TKey>(key, this.comparer);
        this.dictionary[weakKey] = WeakReference<TValue>.Create(value);
    }

    public override void Clear() {
        this.dictionary.Clear();
    }

    public override IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() {
        foreach (KeyValuePair<object, WeakReference<TValue>> kvp in this.dictionary) {
            WeakReference<TKey> weakKey = (WeakReference<TKey>)(kvp.Key);
            WeakReference<TValue> weakValue = kvp.Value;
            TKey key = weakKey.Target;
            TValue value = weakValue.Target;
            if (weakKey.IsAlive && weakValue.IsAlive)
                yield return new KeyValuePair<TKey, TValue>(key, value);
        }
    }

    // Removes the left-over weak references for entries in the dictionary
    // whose key or value has already been reclaimed by the garbage
    // collector. This will reduce the dictionary's Count by the number
    // of dead key-value pairs that were eliminated.
    public void RemoveCollectedEntries() {
        List<object> toRemove = null;
        foreach (KeyValuePair<object, WeakReference<TValue>> pair in this.dictionary) {
            WeakReference<TKey> weakKey = (WeakReference<TKey>)(pair.Key);
            WeakReference<TValue> weakValue = pair.Value;

            if (!weakKey.IsAlive || !weakValue.IsAlive) {
                if (toRemove == null)
                    toRemove = new List<object>();
                toRemove.Add(weakKey);
            }
        }

        if (toRemove != null) {
            foreach (object key in toRemove)
                this.dictionary.Remove(key);
        }
    }
} 

Implementing IDictionary[TKey, TValue] Isn't Trivial

MSDNArchive — Sun, 04 Jun 2006 14:39:00 GMT

I recently needed a dictionary which uses weak references to store both its keys and values, but which otherwise tried its hardest to look and feel just like any other IDictionary<TKey, TValue>. Since there's no such collection available in the BCL, I set out to build  it. I soon discovered that there's a fair bit of plumbing required to implement IDictionary<TKey,TValue> if your underlying storage is at all different from Dictionary<TKey,TValue>. I decided to factor the work out in to two separate chunks. The first chunk was to write an abstract base class which provides as much of the plumbing as possible and defers to the subclass wherever the underlying representation is critical to the implementation.

The class reduces the task of building a new dictionary down to the following abstract methods:

   int Count { get; }
   void Clear();
   void Add(TKey key, TValue value);
   bool ContainsKey(TKey key);
   bool Remove(TKey key);
   bool TryGetValue(TKey key, out TValue value);
   IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
   void SetValue(TKey key, TValue value);

[Update: I renamed SetEntry to SetValue for symmetry with TryGetValue.]

Anyhow, here's the code. Let me know what you think....

/// <summary>
/// Represents a dictionary mapping keys to values.
/// </summary>
/// 
/// <remarks>
/// Provides the plumbing for the portions of IDictionary<TKey,
/// TValue> which can reasonably be implemented without any
/// dependency on the underlying representation of the dictionary.
/// </remarks>
[DebuggerDisplay("Count = {Count}")]
[DebuggerTypeProxy(PREFIX + "DictionaryDebugView`2" + SUFFIX)]
public abstract class BaseDictionary<TKey, TValue> : IDictionary<TKey, TValue> {
    private const string PREFIX = "System.Collections.Generic.Mscorlib_";
    private const string SUFFIX = ",mscorlib,Version=2.0.0.0,Culture=neutral,PublicKeyToken=b77a5c561934e089";

    private KeyCollection keys;
    private ValueCollection values;

    protected BaseDictionary() { }

    public abstract int Count { get; }
    public abstract void Clear();
    public abstract void Add(TKey key, TValue value);
    public abstract bool ContainsKey(TKey key);
    public abstract bool Remove(TKey key);
    public abstract bool TryGetValue(TKey key, out TValue value);
    public abstract IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator();
    protected abstract void SetValue(TKey key, TValue value);

    public bool IsReadOnly {
        get { return false; }
    }

    public ICollection<TKey> Keys {
        get {
            if (this.keys == null)
                this.keys = new KeyCollection(this);

            return this.keys;
        }
    }

    public ICollection<TValue> Values {
        get {
            if (this.values == null)
                this.values = new ValueCollection(this);

            return this.values;
        }
    }

    public TValue this[TKey key] {
        get {
            TValue value;
            if (!this.TryGetValue(key, out value))
                throw new KeyNotFoundException();

            return value;
        }
        set {
            SetValue(key, value);
        }
    }

    public void Add(KeyValuePair<TKey, TValue> item) {
        this.Add(item.Key, item.Value);
    }

    public bool Contains(KeyValuePair<TKey, TValue> item) {
        TValue value;
        if (!this.TryGetValue(item.Key, out value))
            return false;

        return EqualityComparer<TValue>.Default.Equals(value, item.Value);
    }

    public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex) {
        Copy(this, array, arrayIndex);
    }

    public bool Remove(KeyValuePair<TKey, TValue> item) {
        if (!this.Contains(item))
            return false;

        return this.Remove(item.Key);
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
        return this.GetEnumerator();
    }

    private abstract class Collection<T> : ICollection<T> {
        protected readonly IDictionary<TKey, TValue> dictionary;

        protected Collection(IDictionary<TKey, TValue> dictionary) {
            this.dictionary = dictionary;
        }

        public int Count {
            get { return this.dictionary.Count; }
        }

        public bool IsReadOnly {
            get { return true; }
        }

        public void CopyTo(T[] array, int arrayIndex) {
            Copy(this, array, arrayIndex);
        }

        public virtual bool Contains(T item) {
            foreach (T element in this)
                if (EqualityComparer<T>.Default.Equals(element, item))
                    return true;
            return false;
        }

        public IEnumerator<T> GetEnumerator() {
            foreach (KeyValuePair<TKey, TValue> pair in this.dictionary)
                yield return GetItem(pair);
        }

        protected abstract T GetItem(KeyValuePair<TKey, TValue> pair);

        public bool Remove(T item) {
            throw new NotSupportedException("Collection is read-only.");
        }

        public void Add(T item) {
            throw new NotSupportedException("Collection is read-only.");
        }

        public void Clear() {
            throw new NotSupportedException("Collection is read-only.");
        }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            return this.GetEnumerator();
        }
    }

    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(PREFIX + "DictionaryKeyCollectionDebugView`2" + SUFFIX)]
    private class KeyCollection : Collection<TKey> {
        public KeyCollection(IDictionary<TKey, TValue> dictionary)
            : base(dictionary) { }

        protected override TKey GetItem(KeyValuePair<TKey, TValue> pair) {
            return pair.Key;
        }
        public override bool Contains(TKey item) {
            return this.dictionary.ContainsKey(item);
        }
    }

    [DebuggerDisplay("Count = {Count}")]
    [DebuggerTypeProxy(PREFIX + "DictionaryValueCollectionDebugView`2" + SUFFIX)]
    private class ValueCollection : Collection<TValue> {
        public ValueCollection(IDictionary<TKey, TValue> dictionary)
            : base(dictionary) { }

        protected override TValue GetItem(KeyValuePair<TKey, TValue> pair) {
            return pair.Value;
        }
    }

    private static void Copy<T>(ICollection<T> source, T[] array, int arrayIndex) {
        if (array == null)
            throw new ArgumentNullException("array");

        if (arrayIndex < 0 || arrayIndex > array.Length)
            throw new ArgumentOutOfRangeException("arrayIndex");

        if ((array.Length - arrayIndex) < source.Count)
            throw new ArgumentException("Destination array is not large enough. Check array.Length and arrayIndex.");

        foreach (T item in source)
            array[arrayIndex++] = item;
    }
} 

Think Twice Before Throwing from Attribute Constructors

MSDNArchive — Wed, 26 Apr 2006 08:42:00 GMT

I had an interesting discussion recently about a subtle issue with custom attributes and I thought I'd share my conclusion. The question is whether it's a good practice to throw ArgumentException from an attribute constructor as in the following example:

[AttributeUsage(AttributeTargets.All)]
public class MyAttribute : Attribute {
    private string value;
    public MyAttribute(string value) {
       if (value == null) throw new ArgumentNullException("value");
       this.value = value;
    }
    public string Value {
        get { return this.value; }
    }
}

The idea is to express that a null 'value' argument represents an invalid use of MyAttribute. However, this error will not be surfaced at compile time when the malformed attrtibute is applied; it will be thrown at runtime when the attribute is retrieved via GetCustomAttributes. However, throwing ArgumentException then is inappropriate because there's nothing the caller can do to prevent it. Attribute constructors should capture their arguments as-is and let consumers handle the validation.

Mmm... Hungarian Notation...

MSDNArchive — Fri, 14 Apr 2006 07:08:00 GMT

I'm not a fan of Hungarian notation for variable names, particularly the variety where static type information is encrypted into impenetrable acronyms and repeated redundantly with every variable access. As the authors of The Pragmatic Programmer would say, it violates the DRY (Don't Repeat Yourself) principle. If you change the variable's type, then you need to make sure to rename the variable as well or the Hungarian notation becomes a trap to mislead those who maintain the code in the future.

Let's take a look at an example of Hungarian notation gone bad. I stumbled on to it when a colleague pointed me to this blog post about FxCop saving the day from misleading documentation. (FxCop has a handy rule which can flag the most common source of portability bugs in managed code: passing incorrectly sized integer arguments to common Win32 API via P/Invoke.) The troublesome API in question is HeapCreate which (assuming you don't pick up the WinCE docs by mistake) has the following signature:

HANDLE HeapCreate(
    DWORD flOptions,
    SIZE_T dwInitialSize,
    SIZE_T dwMaximumSize);

Wait a second; doesn't the dw prefix mean DWORD, which is always 4 bytes wide whereas SIZE_T is 4 bytes wide on 32-bits platforms and 8 bytes wide on 64-bit platforms? I presume that the initial and maximum size arguments were first typed as DWORD, but needed to become SIZE_T to support the larger address space in the move to 64-bit. Unfortunately, nobody bothered to change the parameter names accordingly.

For the record, the correct P/Invoke declaration for HeapCreate is as follows:

[DllImport("kernel32.dll", SetLastError=true)]
static extern IntPtr HeapCreate(
    Int32 options,
    UIntPtr initialSize,
    UIntPtr maximumSize);

Notice how I left out the Hungarian notation. Good riddance!

Hello? Is this thing on?

MSDNArchive — Thu, 13 Apr 2006 15:19:00 GMT

Allow me to introduce myself...

I'm a developer on the Visual Studio Code Analysis team. I joined Microsoft in September of 2003 after completing my Computer Engineering degree at McGill University in my home town of Montreal and I've been working on FxCop and managed code analysis ever since.

We've recently revived our team blog and since I've always found blogs.msdn.com to be an invaluable resource, I'm inspired to start this blog of my own. I'll be sharing my thoughts on code analysis, managed code, and other (incidentally) related topics.