Dictionary lookup throws "Index was outside the bounds of the array"

Question

I received an error report which seems to come from the following code:

public class AnimationChannelCollection : ReadOnlyCollection<BoneKeyFrameCollection>
{
        private Dictionary<string, BoneKeyFrameCollection> dict =
            new Dictionary<string, BoneKeyFrameCollection>();

        private ReadOnlyCollection<string> affectedBones;

       // This immutable data structure should not be created by the library user
        internal AnimationChannelCollection(IList<BoneKeyFrameCollection> channels)
            : base(channels)
        {
            // Find the affected bones
            List<string> affected = new List<string>();
            foreach (BoneKeyFrameCollection frames in channels)
            {
                dict.Add(frames.BoneName, frames);
                affected.Add(frames.BoneName);
            }
            affectedBones = new ReadOnlyCollection<string>(affected);

        }

        public BoneKeyFrameCollection this[string boneName]
        {           
            get { return dict[boneName]; }
        }
}

---

This is the calling code that reads the dictionary:

public override Matrix GetCurrentBoneTransform(BonePose pose)
    {
        BoneKeyFrameCollection channel =  base.AnimationInfo.AnimationChannels[pose.Name];       
    }

---

This is the code that creates the dictionary, happens on startup:

// Reads in processed animation info written in the pipeline
internal sealed class AnimationReader :   ContentTypeReader<AnimationInfoCollection>
{
    /// <summary> 
    /// Reads in an XNB stream and converts it to a ModelInfo object
    /// </summary>
    /// <param name="input">The stream from which the data will be read</param>
    /// <param name="existingInstance">Not used</param>
    /// <returns>The unserialized ModelAnimationCollection object</returns>
    protected override AnimationInfoCollection Read(ContentReader input, AnimationInfoCollection existingInstance)
    {
        AnimationInfoCollection dict = new AnimationInfoCollection();
        int numAnimations = input.ReadInt32();

        /* abbreviated */

        AnimationInfo anim = new AnimationInfo(animationName, new AnimationChannelCollection(animList));

    }
}

The error is:

Index was outside the bounds of the array.

Line: 0

at System.Collections.Generic.Dictionary`2.FindEntry(TKey key)

at System.Collections.Generic.Dictionary`2.get_Item(TKey key)

at Xclna.Xna.Animation.InterpolationController.GetCurrentBoneTransform(BonePose pose)

I would have expected a KeyNotFoundException with the wrong key, but instead I get "Index was outside the bounds of the array". I don't understand how I could get that exception from the above code?

The code is singlethreaded by the way.

Solution

A "Index was outside the bounds of the array." error on a Dictionary (or anything in the System.Collections namespace) when the documentation says the error should not be thrown is always caused by you violating thread safety.

All collections in the System.Collections namespace allow only one of two operations happen

• Unlimited concurrent readers, 0 writers.
• 0 readers, 1 writer.

You either must synchronize all access to the dictionary using a ReaderWriterLockSlim which gives the exact behavior described above

private Dictionary<string, BoneKeyFrameCollection> dict =
            new Dictionary<string, BoneKeyFrameCollection>();
private ReaderWriterLockSlim dictLock = new ReaderWriterLockSlim();

public BoneKeyFrameCollection this[string boneName]
{           
    get 
    { 
        try
        {
            dictLock.EnterReadLock();
            return dict[boneName]; 
        }
        finally
        {
            dictLock.ExitReadLock();
        }
    }
}


 public void UpdateBone(string boneName, BoneKeyFrameCollection col)
 {  
    try
    {
        dictLock.EnterWriteLock();
        dict[boneName] = col; 
    }
    finally
    {
        dictLock.ExitWriteLock();
    }
 }

or replace your Dictionary<string, BoneKeyFrameCollection> with a ConcurrentDictionary<string, BoneKeyFrameCollection>

private ConcurrentDictionary<string, BoneKeyFrameCollection> dict =
            new ConcurrentDictionary<string, BoneKeyFrameCollection>();

 public BoneKeyFrameCollection this[string boneName]
 {           
    get 
    { 
        return dict[boneName];
    }
 }

 public void UpdateBone(string boneName, BoneKeyFrameCollection col)
 {  
    dict[boneName] = col;
 }

---

UPDATE: I really don't see how the code you have shown could have caused this. Here is the source code for the function that is causing it to be thrown.

private int FindEntry(TKey key) {
    if( key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null) {
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i;
        }
    }
    return -1;
}

The only way that code throws a ArgumentOutOfRangeException is if you try to index a illegal record in buckets or entries.

Because your key is a string and strings are immutable we can rule out a hashcode value for a key that was changed after the key was put in to the dictionary. All that remains is a buckets[hashCode % buckets.Length] call and a few entries[i] calls.

The only way buckets[hashCode % buckets.Length] could fail is if the instance of buckets was replaced between the buckets.Length property call and the this[int index] indexer call. The only time buckets gets replaced is when Resize is called internally by Insert, Initialize is called by the constructor/first call to Insert, or on a call to OnDeserialization.

The only places Insert gets called is the setter for this[TKey key], the public Add function, and inside OnDeserialization. The only way for buckets to be replaced is if we are making calls to one of the three listed functions at the same moment the FindEntry call happens on the other thread during the buckets[hashCode % buckets.Length] call.

The only way we could get a bad entries[i] call is if entries gets swapped out on us (follows the same rules as buckets) or we get a bad value for i. The only way to get a bad value for i is if entries[i].next returns a bad value. The only way to get a bad value from entries[i].next is to have concurrent operations going on during Insert, Resize, or Remove.

The only thing I can think of is either something is going wrong on a OnDeserialization call and you have bad data to start with before deserialization or there is more code to AnimationChannelCollection that affects the dictionary that you are not showing us.