A bunch of people (Eric, Wes, Joe, etc) have been writing about the wonders of immutable data structures lately.  A friend who no longer works at MS suggested that I should dig up some code that he wrote with some feedback from me to try and help you enforce immutability in your code.

We started with the idea that we could use attributes to mark types as immutable.  Then we could write some code that enforces that the Immutable attribute is actually satisfied.  The rules are:

  1. The base type meets the rules.
  2. The members are marked 'readonly'
  3. The types of the members meet the rules.

In practice, this fails very quickly, as soon as you bring in type that you didn't write, so there are some special exceptions:

  1. Builtin types get a pass
  2. 'enum' types get a pass
  3. There's a whitelist of types in .Net Framework that are immutable, but lack the attribute.
  4. You can put the [Immutable] attribute on a _field_, indicating that the usage of this field is correct wrt. immutability, even though the type of the field isn't itself immutable.
  5. You can put [Immutable (OnFaith=true)] on a type to say that a type should be assume to meet the rules without further inspection.
  6. In your test you can pass in an additional whitelist of types that you don't own, aren’t part of .Net Framework, and are immutable.

Here's the code for those who are interested.  I'll start with an example of problematic code we'd like to find.  There is a problem with both of the types below.  'MutableStruct' is a problem because any time you have a mutable value type you have a problem in my opinion.  It's far too easy to mutate the wrong copy of a struct, and spend ages trying to figure out where the bug is.  'MutableClass' is a problem because it lies.  The author placed the ImmutableAttribute on it, signifying that they intend the type to be immutable, but it's actually not.  The sort of time this is an issue is when you have a large amount of code which depends on the fact that MutableClass is immutable, and then you try to make a change that makes it mutable.  Without a system like this, you may not realize that the original author intended MutableClass to be immutable.

struct MutableStruct
{
    public int field;
}

[Immutable]
class MutableClass
{
    public int mutableField;
}

Next, let's write some unit tests, to ensure that we don't ship this code.  There are two unit tests here.  The first one ensures that all structs are marked with the immutable attribute.  The second verifies that all types marked with the ImmutableAttribute actually are immutable.  It does that by calling into some code directly in the attribute, which is below.  You might ask why this wasn't implemented as a Code Analysis, (aka FxCop) rule.  The simple answer is that Jay and I were familiar with reflection and the unit testing framework, but not familiar with writing FxCop rules.  If anyone wants to translate this into FxCop rules, I'd be interested in what that looks like.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Text;
using Microsoft.VisualStudio.TestTools.UnitTesting;

[TestClass]
public class Immutable_Tests
{
    private IEnumerable<Assembly> AssembliesToTest
    {
        get { return new[] { System.Reflection.Assembly.GetExecutingAssembly() }; }
    }

    [TestMethod]
    // It's particularly important that 'struct' types are immutable.
    // for a short discussion, see http://blogs.msdn.com/jaybaz_ms/archive/2004/06/10/153023.aspx
    public void EnsureStructsAreImmutableTest()
    {
        var mutableStructs = from type in AssembliesToTest.GetTypes()
                             where IsMutableStruct(type)
                             select type;

        if (mutableStructs.Any())
        {
            Assert.Fail("'{0}' is a value type, but was not marked with the [Immutable] attribute", mutableStructs.First().FullName);
        }
    }
    [TestMethod]
    // ensure that any type marked [Immutable] has fields that are all immutable
    public void EnsureImmutableTypeFieldsAreMarkedImmutableTest()
    {
        try
        {
            ImmutableAttribute.VerifyTypesAreImmutable(AssembliesToTest);
        }
        catch (ImmutableAttribute.ImmutableFailureException ex)
        {
            Console.Write(FormatExceptionForAssert(ex));
            Assert.Fail("'{0}' failed the immutability test.  See output for details.", ex.Type.Name);
        }
    }
    internal static bool IsMutableStruct(Type type)
    {
        if (!type.IsValueType) { return false; }
        if (type.IsEnum) { return false; }
        if (type.IsSpecialName) { return false; }
        if (type.Name.StartsWith("__")) { return false; }
        if (ReflectionHelper.TypeHasAttribute<ImmutableAttribute>(type)) { return false; }
        return true;
    }

    static string FormatExceptionForAssert(Exception ex)
    {
        StringBuilder sb = new StringBuilder();

        string indent = "";

        for (; ex != null; ex = ex.InnerException)
        {
            sb.Append(indent);
            sb.AppendLine(ex.Message);

            indent = indent + "    ";
        }

        return sb.ToString();
    }
}

 

Without further ado, here's the ImmutableAttribute itself.  Note that some of the code is written to use the "ReflectionHelper", which is a utility class that provides some (IMO) useful wrappers around System.Reflection.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;

[AttributeUsage(AttributeTargets.Class | AttributeTargets.Struct, AllowMultiple = false, Inherited = true)]
[Serializable]
public sealed class ImmutableAttribute : Attribute
{

    // in some cases, a type is immutable but can't be proven as such.
    // in these cases, the developer can mark the type with [Immutable(true)]
    // and the code below will take it on faith that the type is immutable,
    // instead of testing explicitly.
    //
    // A common example is a type that contains a List<T>, but doesn't 
    // modify it after construction.
    //
    // TODO: replace this with a per-field attribute, to allow the 
    // immutability test to run over the rest of the type.
    public bool OnFaith;

    /// <summary>
    /// Ensures that all types in 'assemblies' that are marked 
    /// [Immutable] follow the rules for immutability.
    /// </summary>
    /// <exception cref="ImmutableFailureException">Thrown if a mutability issue appears.</exception>
    [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1002:DoNotExposeGenericLists")]
    public static void VerifyTypesAreImmutable(IEnumerable<Assembly> assemblies, params Type[] whiteList)
    {
        var typesMarkedImmutable = from type in assemblies.GetTypes()
                                   where IsMarkedImmutable(type)
                                   select type;

        foreach (var type in typesMarkedImmutable)
        {
            VerifyTypeIsImmutable(type, whiteList);
        }
    }

    static bool IsMarkedImmutable(Type type)
    {
        return ReflectionHelper.TypeHasAttribute<ImmutableAttribute>(type);
    }

    class WritableFieldException : ImmutableFailureException
    {
        protected WritableFieldException(SerializationInfo serializationInfo, StreamingContext streamingContext)
            : base(serializationInfo, streamingContext)
        {
        }

        internal WritableFieldException(FieldInfo fieldInfo)
            : base(fieldInfo.DeclaringType, FormatMessage(fieldInfo))
        {
        }

        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Globalization", "CA1305:SpecifyIFormatProvider", MessageId = "System.String.Format(System.String,System.Object,System.Object)")]
        static string FormatMessage(FieldInfo fieldInfo)
        {
            return string.Format("'{0}' is mutable because field '{1}' is not marked 'readonly'.", fieldInfo.DeclaringType, fieldInfo.Name);
        }
    }

    class MutableFieldException : ImmutableFailureException
    {
        protected MutableFieldException(SerializationInfo serializationInfo, StreamingContext streamingContext)
            : base(serializationInfo, streamingContext)
        {
        }

        internal MutableFieldException(FieldInfo fieldInfo, Exception inner)
            : base(fieldInfo.DeclaringType, FormatMessage(fieldInfo), inner)
        {
        }

        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Globalization", "CA1305:SpecifyIFormatProvider", MessageId = "System.String.Format(System.String,System.Object,System.Object,System.Object)")]
        static string FormatMessage(FieldInfo fieldInfo)
        {
            return string.Format("'{0}' is mutable because '{1}' of type '{2}' is mutable.", fieldInfo.DeclaringType, fieldInfo.Name, fieldInfo.FieldType);
        }
    }

    class MutableBaseException : ImmutableFailureException
    {
        protected MutableBaseException(SerializationInfo serializationInfo, StreamingContext streamingContext)
            : base(serializationInfo, streamingContext)
        {
        }

        internal MutableBaseException(Type type, Exception inner)
            : base(type, FormatMessage(type), inner)
        {
        }

        [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Globalization", "CA1305:SpecifyIFormatProvider", MessageId = "System.String.Format(System.String,System.Object,System.Object)")]
        static string FormatMessage(Type type)
        {
            return string.Format("'{0}' is mutable because its base type ('[{1}]') is mutable.", type, type.BaseType);
        }
    }

    [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Usage", "CA2237:MarkISerializableTypesWithSerializable")]
    [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1032:ImplementStandardExceptionConstructors")]
    public class ImmutableFailureException : Exception
    {
        public readonly Type Type;

        protected ImmutableFailureException(SerializationInfo serializationInfo, StreamingContext streamingContext)
            : base(serializationInfo, streamingContext)
        {
        }

        internal ImmutableFailureException(Type type, string message, Exception inner)
            : base(message, inner)
        {
            this.Type = type;
        }

        internal ImmutableFailureException(Type type, string message)
            : base(message)
        {
            this.Type = type;
        }
    }

    /// <summary>
    /// Ensures that 'type' follows the rules for immutability
    /// </summary>
    /// <exception cref="ImmutableFailureException">Thrown if a mutability issue appears.</exception>
    [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Design", "CA1002:DoNotExposeGenericLists")]
    public static void VerifyTypeIsImmutable(Type type, IEnumerable<Type> whiteList)
    {
        if (whiteList.Contains(type))
        {
            return;
        }

        if (IsWhiteListed(type))
        {
            return;
        }

        try
        {
            VerifyTypeIsImmutable(type.BaseType, whiteList);
        }
        catch (ImmutableFailureException ex)
        {
            throw new MutableBaseException(type, ex);
        }

        foreach (FieldInfo fieldInfo in ReflectionHelper.GetAllDeclaredInstanceFields(type))
        {
            if ((fieldInfo.Attributes & FieldAttributes.InitOnly) == 0)
            {
                throw new WritableFieldException(fieldInfo);
            }

            // if it's marked with [Immutable], that's good enough, as we
            // can be sure that these tests will all be applied to this type
            if (!IsMarkedImmutable(fieldInfo.FieldType))
            {
                try
                {
                    VerifyTypeIsImmutable(fieldInfo.FieldType, whiteList);
                }
                catch (ImmutableFailureException ex)
                {
                    throw new MutableFieldException(fieldInfo, ex);
                }
            }
        }
    }

    static bool IsWhiteListed(Type type)
    {
        if (type == typeof(Object))
        {
            return true;
        }

        if (type == typeof(String))
        {
            return true;
        }

        if (type == typeof(Guid))
        {
            return true;
        }

        if (type.IsEnum)
        {
            return true;
        }

        // bool, int, etc.
        if (type.IsPrimitive)
        {
            return true;
        }

        // override all checks on this type if [ImmutableAttribute(OnFaith=true)] is set
        ImmutableAttribute immutableAttribute = ReflectionHelper.GetCustomAttribute<ImmutableAttribute>(type);
        if (immutableAttribute != null && immutableAttribute.OnFaith)
        {
            return true;
        }

        return false;
    }
}

[Serializable]
internal static class ReflectionHelper
{
    /// <summary>
    /// Find all types in 'assembly' that derive from 'baseType'
    /// </summary>
    /// <owner>jayBaz</owner>
    internal static IEnumerable<Type> FindAllTypesThatDeriveFrom<TBase>(Assembly assembly)
    {
        return from type in assembly.GetTypes()
               where type.IsSubclassOf(typeof(TBase))
               select type;
    }

    /// <summary>
    /// Check if the given type has the given attribute on it.  Don't look at base classes.
    /// </summary>
    /// <owner>jayBaz</owner>
    internal static bool TypeHasAttribute<TAttribute>(Type type)
        where TAttribute : Attribute
    {
        return Attribute.IsDefined(type, typeof(TAttribute));
    }

    // I find that the default GetFields behavior is not suitable to my needs
    internal static IEnumerable<FieldInfo> GetAllDeclaredInstanceFields(Type type)
    {
        return type.GetFields(BindingFlags.Public | BindingFlags.NonPublic | BindingFlags.Instance | BindingFlags.DeclaredOnly);
    }

    /// <summary>
    /// A typesafe wrapper for Attribute.GetCustomAttribute
    /// </summary>
    /// <remarks>TODO: add overloads for Assembly, Module, and ParameterInfo</remarks>
    internal static TAttribute GetCustomAttribute<TAttribute>(MemberInfo element)
        where TAttribute : Attribute
    {
        return (TAttribute)Attribute.GetCustomAttribute(element, typeof(TAttribute));
    }

    /// <summary>
    /// All types across multiple assemblies
    /// </summary>
    public static IEnumerable<Type> GetTypes(this IEnumerable<Assembly> assemblies)
    {
        return from assembly in assemblies
               from type in assembly.GetTypes()
               select type;
    }
}

 

What do you think?  Is this sort of verification of immutability useful?

Technorati Tags: ,,,