Results 1 to 18 of 18

Thread: [RESOLVED] Interesting Dictionary Bug

  1. #1

    Thread Starter
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,235

    Resolved [RESOLVED] Interesting Dictionary Bug

    There is a bug in the following code, but I'm not interested in that:

    Code:
    For Each ky In mPinInitDict.Keys
        mPinInitDict(ky) = ky.Location 'Just set the current location as the stored location
    Next
    What interests me is that this loop fails with an exception that the collection was modified and that the enumeration operation may not execute.

    That exception normally happens when you add or remove something from a collection in a For Each loop. In this case, I am changing a property of one of the keys. I am not adding or removing items from the collection, nor am I altering the key in the dictionary, which is what the loop is iterating through. All I am changing is the value associated with the key.

    In fact, because of the underlying bug, I'm not actually changing anything at all. This code works:

    Code:
     For Each ky In mPinDict.Keys
         mPinInitDict(ky) = ky.Location 'Just set the current location as the stored location
     Next
    The PinInitDict just holds the initial locations tied to pins. Those pins can be dragged and dropped, which will change their locations. In the initial code, ky.Location is the Location property of the pin. The PinDict is a second dictionary that has the exact same keys as the PinInitDict. In fact, it doesn't have to be a dictionary at all, because the value is never used. It could just as easily be a simple List(of Pin).

    Still, the mPinInitDict and the mPinDict have the same keys. Those pins are reference types, so it's not like the keys collections of the two dictionaries have different objects that look the same, they are the same pins, which is why I can use the key of one dictionary as a key in the other dictionary. These two lines:

    For Each ky In mPinInitDict.Keys

    and

    For Each ky In mPinDict.Keys

    will return the same objects in the same order. In either case, this line:

    mPinInitDict(ky) = ky.Location

    does not alter the enumerator in any way. What it alters is the value associated with the key. The only difference between the two codes is the collection that the reference is obtained from. It's the same reference in both cases, and the reference isn't being changed in either case, only the value is being changed.

    So, why is this an exception?
    My usual boring signature: Nothing

  2. #2
    Super Moderator dday9's Avatar
    Join Date
    Mar 2011
    Location
    South Louisiana
    Posts
    9,677

    Re: Interesting Dictionary Bug

    It makes sense that there is no exception because you're not altering the collection that is being iterated(mPinDict), you're altering another collection(mPinInitDict).

  3. #3
    PowerPoster
    Join Date
    Oct 2010
    Posts
    2,141

    Re: Interesting Dictionary Bug

    The coding reason behind this is that the dictionary version field gets incremented when you set the item. Follow the key lines highlighted in red.

    This code:
    Code:
    For Each ky As Int32 In dict.Keys
       dict.Item(ky) = "bye"
    Next
    Compiled/Decompiled to this:

    Code:
        Try 
            enumerator = dictionary.Keys.GetEnumerator
            Do While enumerator.MoveNext
                Dim current As Integer = enumerator.Current
                dictionary.Item(current) = "bye"
            Loop
        Finally
            enumerator.Dispose
        End Try
    End Sub
    Code:
    Public Default Property Item(ByVal key As TKey) As TValue
        <__DynamicallyInvokable> _
        Get
            Dim index As Integer = Me.FindEntry(key)
            If (index >= 0) Then
                Return Me.entries(index).value
            End If
            ThrowHelper.ThrowKeyNotFoundException
            Return CType(Nothing, TValue)
        End Get
        <__DynamicallyInvokable, TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")> _
        Set(ByVal value As TValue)
            Me.Insert(key, value, False)
        End Set
    End Property
    Code:
    Private Sub Insert(ByVal key As TKey, ByVal value As TValue, ByVal add As Boolean)
        Dim freeList As Integer
        If (key Is Nothing) Then
            ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key)
        End If
        If (Me.buckets Is Nothing) Then
            Me.Initialize(0)
        End If
        Dim num As Integer = (Me.comparer.GetHashCode(key) And &H7FFFFFFF)
        Dim index As Integer = (num Mod Me.buckets.Length)
        Dim num3 As Integer = 0
        Dim i As Integer = Me.buckets(index)
        Do While (i >= 0)
            If ((Me.entries(i).hashCode = num) AndAlso Me.comparer.Equals(Me.entries(i).key, key)) Then
                If add Then
                    ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate)
                End If
                Me.entries(i).value = value
                Me.version += 1
                Return
            End If
            num3 += 1
            i = Me.entries(i).next
        Loop
        If (Me.freeCount > 0) Then
            freeList = Me.freeList
            Me.freeList = Me.entries(freeList).next
            Me.freeCount -= 1
        Else
            If (Me.count = Me.entries.Length) Then
                Me.Resize
                index = (num Mod Me.buckets.Length)
            End If
            freeList = Me.count
            Me.count += 1
        End If
        Me.entries(freeList).hashCode = num
        Me.entries(freeList).next = Me.buckets(index)
        Me.entries(freeList).key = key
        Me.entries(freeList).value = value
        Me.buckets(index) = freeList
        Me.version += 1
        If ((num3 > 100) AndAlso HashHelpers.IsWellKnownEqualityComparer(Me.comparer)) Then
            Me.comparer = DirectCast(HashHelpers.GetRandomizedEqualityComparer(Me.comparer), IEqualityComparer(Of TKey))
            Me.Resize(Me.entries.Length, True)
        End If
    End Sub
    Code:
        <__DynamicallyInvokable> _
        Public Function MoveNext() As Boolean
            If (Me.version <> Me.dictionary.version) Then
                ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion)
            End If
            Do While (Me.index < Me.dictionary.count)
                If (Me.dictionary.entries(Me.index).hashCode >= 0) Then
                    Me.currentKey = Me.dictionary.entries(Me.index).key
                    Me.index += 1
                    Return True
                End If
                Me.index += 1
            Loop
            Me.index = (Me.dictionary.count + 1)
            Me.currentKey = CType(Nothing, TKey)
            Return False
        End Function
    So should the Dictionary version change because you change one of the values? I would say yes.

    Should there be another internal version field that only applies to changes in the Keys list that would be checked in the enumerator? -- Probably so.

    Edit: originally highlighted wrong incrementation of version in Insert method
    Last edited by TnTinMN; Jan 9th, 2015 at 04:10 PM.

  4. #4

    Thread Starter
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,235

    Re: Interesting Dictionary Bug

    That's pretty interesting code, for more reasons than the fact that it does rather explain what is going on. I'm intrigued to see that MS is using multiple return points, which I don't mind, though some feel it is wrong. I'm also interested in seeing the highly uninspired variables names, such as num and num3.
    My usual boring signature: Nothing

  5. #5

    Thread Starter
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,235

    Re: Interesting Dictionary Bug

    Quote Originally Posted by dday9 View Post
    It makes sense that there is no exception because you're not altering the collection that is being iterated(mPinDict), you're altering another collection(mPinInitDict).
    Actually, I'm technically not altering either collection in ways that I thought would matter. I don't deal with the version number, nor do I see the point to it, at a glance, but that's where the change lies. Dictionaries just work a bit different under the hood from some other collections.
    My usual boring signature: Nothing

  6. #6
    Hyperactive Member
    Join Date
    Sep 2014
    Posts
    404

    Re: [RESOLVED] Interesting Dictionary Bug

    on an unrelated note, how can you get the decompiled code from MS prebuilt functions?

  7. #7
    PowerPoster
    Join Date
    Oct 2010
    Posts
    2,141

    Re: Interesting Dictionary Bug

    Quote Originally Posted by Shaggy Hiker View Post
    That's pretty interesting code, for more reasons than the fact that it does rather explain what is going on. I'm intrigued to see that MS is using multiple return points, which I don't mind, though some feel it is wrong. I'm also interested in seeing the highly uninspired variables names, such as num and num3.
    That's not the original code. It from using Redgate's Reflector decompiler.

    The original in C# can be viewed here:
    http://referencesource.microsoft.com...599058f8d79be0

  8. #8
    Hyperactive Member
    Join Date
    Sep 2014
    Posts
    404

    Re: [RESOLVED] Interesting Dictionary Bug

    Thank you for the link that is a very useful website which I wasn't aware of.

    is the code which you posted not taken from this site then?

  9. #9
    PowerPoster
    Join Date
    Oct 2010
    Posts
    2,141

    Re: [RESOLVED] Interesting Dictionary Bug

    Quote Originally Posted by Leary222 View Post
    Thank you for the link that is a very useful website which I wasn't aware of.

    is the code which you posted not taken from this site then?
    I a roundabout yes, but it was generated by decompiling the .Net library using Reflector.

  10. #10
    Hyperactive Member
    Join Date
    Sep 2014
    Posts
    404

    Re: [RESOLVED] Interesting Dictionary Bug

    right I see, is the MS code in the format which you gave it not available direct from MS because looking through that website everything seams to be self referencing an no actual procedures or event handling as shown above, why is this?

  11. #11
    PowerPoster
    Join Date
    Oct 2010
    Posts
    2,141

    Re: [RESOLVED] Interesting Dictionary Bug

    Quote Originally Posted by Leary222 View Post
    right I see, is the MS code in the format which you gave it not available direct from MS because looking through that website everything seams to be self referencing an no actual procedures or event handling as shown above, why is this?
    If by format you mean in as VB.Net code, you are going to be out of luck for almost all code if not all code. I think that a few of the VB support libraries where written in VB, but I can not remember for certain.

    C# is MS's language of choice for .Net. I presented the code converted to VB because this is a VB forum. The original (C#) source for everything I showed, with the exception of my own code fragment, can be easily found by navigating that link.

  12. #12
    Hyperactive Member
    Join Date
    Sep 2014
    Posts
    404

    Re: [RESOLVED] Interesting Dictionary Bug

    In this case why would any one use reflector soft wear ?

  13. #13

    Thread Starter
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,235

    Re: [RESOLVED] Interesting Dictionary Bug

    Well, TnTinMN used it to answer my question. Is that not good enough?
    My usual boring signature: Nothing

  14. #14
    Hyperactive Member
    Join Date
    Sep 2014
    Posts
    404

    Re: [RESOLVED] Interesting Dictionary Bug

    Well yes obviously, however if this source code is avalible direct from MS why are decompilers required ?

  15. #15

    Thread Starter
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,235

    Re: [RESOLVED] Interesting Dictionary Bug

    Ah, yeah, that's a point. My understanding is that the code isn't available to everybody, or it wasn't availabel to anybody (outside of MS) at some point in the past.
    My usual boring signature: Nothing

  16. #16
    PowerPoster
    Join Date
    Oct 2010
    Posts
    2,141

    Re: [RESOLVED] Interesting Dictionary Bug

    Quote Originally Posted by Leary222 View Post
    Well yes obviously, however if this source code is avalible direct from MS why are decompilers required ?
    They are not required, but they sure are a nice tool to have.

    Here are few reasons to have/use one.

    1. As Shaggy said, the code was not always available. MS just recently open sourced a lot of the .Net libraries.

    2. Use as a learning tool. This was initially my primary use. It is nice to see have someone else might have done something.

    3. Just because you write code that should not generate an error, it does not mean that compiler will not translate it into something else that may generate an error.

    Here is simple (but contrived) case.

    My Code:
    Code:
    Private Sub test1()
      ' Int32.MaxValue=2147483647
       For i As Int32 = Int32.MaxValue - 1 To Int32.MaxValue
       Next
    End Sub
    Nothing here that should cause an "An unhandled exception of type 'System.OverflowException'" right?

    The loop limit is set the maximum for an integer so how could it ever exceed that maximum limit?

    Well here is what the compiler converts that code to:
    Code:
    Private Sub test1()
        Dim num As Integer = &H7FFFFFFE
        Do
            num += 1
        Loop While (num <= &H7FFFFFFF)
    End Sub
    After the first pass, num = Int32.MaxValue and it loops for a second pass. However, now it is trying to add one(1) to Int32.MaxValue and an overflow is generated. Well at least it throws an error if overflow checking is enabled (the default for VB projects).

    Now consider the case where this logic was buried in a library that I thought was rock solid and I disabled integer overflow checking to increase performance. The variable num would increment and its value would roll over to Int32.MinValue and the loop would continue on forever as the exit condition would never to true. Not good!

    As I said, this was a contrived example because I learned a long time ago that For-Next loops compile this way (see my reason #2). However if I did not have this knowledge, I sure could waste a lot of time cussing at my computer and MS for this error that should not exist.

  17. #17

    Thread Starter
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    35,235

    Re: [RESOLVED] Interesting Dictionary Bug

    Hunh. I never thought of using reflector for that. I've known that For...Next loops leave the iterator at 1 greater than the upper limit for a long time. I always kind of figured that the Next acted as a iterator+=1, though in fact, the For and the Next are really just constructs of hte language. I thought loops always inverted internally such that you are always counting down to 0 in one register (cx, I believe, back in the day), and once the counter hit 0, the zero flag was set. I haven't looked at that in two decades, though, so I may have it wrong.
    My usual boring signature: Nothing

  18. #18
    PowerPoster i00's Avatar
    Join Date
    Mar 2002
    Location
    1/2 way accross the galaxy.. and then some
    Posts
    2,347

    Re: [RESOLVED] Interesting Dictionary Bug

    Quote Originally Posted by Leary222 View Post
    Well yes obviously, however if this source code is avalible direct from MS why are decompilers required ?
    Some also allow decompiling directly to other languages (such as VB.Net), and these generally work better than using reference source then using online code converters.

    Kris

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  



Click Here to Expand Forum to Full Width