C#•11mo ago

Dictionary cant find via ContainsKey but it does exist

Am i dumb or are dictionaries broken How could this even happen? I see via the debugger that the key i want is in the dictionary but when i use ContainsKey it doesnt find it, huh? Im real confused

7 Replies

turnerOP•11mo ago

This is the dictionary in question:

Dictionary<CilInstruction, int> jumpsToInstruction = new Dictionary<CilInstruction, int>();

Dictionary<CilInstruction, int> jumpsToInstruction = new Dictionary<CilInstruction, int>();

the CilInstruction type is from the library AsmResolver which does have its own Equals and GetHashCode which when i manually check produces the correct results and the dict should find it based on that

Arthus•11mo ago

Hello, can you share a bit more about your code? Remember that the ContainsKey will use Object.Equals to find you key in the dictionary.

turnerOP•11mo ago

sure, what else is there to share? I think i shared everything Just to clarify if i do:

jumpsToInstruction.ElementAt(13).Key.GetHashCode() == dstInstruction.GetHashCode()
jumpsToInstruction.ElementAt(13).Key.Equals(dstInstruction)

jumpsToInstruction.ElementAt(13).Key.GetHashCode() == dstInstruction.GetHashCode()
jumpsToInstruction.ElementAt(13).Key.Equals(dstInstruction)

They will both return true, so from what i understand this means that the methods are correctly overridden

Arthus•11mo ago

What I want to see if how you hidratate your Dictionary and where are you trying to do the ContainsKey so I can see if your are doing something wrong So far what I understood is:

var dictionary = new Dictionary<CilIntruction,int>() {somePairs};

var yourLookupKey = //initialization;

Debug.Assert(dictionary.ContainsKey(yourLookupKey) == true); //Here throws

var dictionary = new Dictionary<CilIntruction,int>() {somePairs};

var yourLookupKey = //initialization;

Debug.Assert(dictionary.ContainsKey(yourLookupKey) == true); //Here throws

turnerOP•11mo ago

ah yea, well sadly its not 5 lines but here it is: this is where the lookup gets populated

void ComputeJumpsToInstructions(CilInstructionCollection instructions)
{
    foreach (var instruction in instructions)
    {
        if (instruction.IsBranch())
        {
            if (instruction.OpCode == CilOpCodes.Switch)
            {
                var dstList = instruction.Operand as List<ICilLabel>;

                foreach (var dst in dstList.Cast<CilInstructionLabel>())
                {
                    if (jumpsToInstruction.ContainsKey(dst.Instruction))
                    {
                        jumpsToInstruction[dst.Instruction]++;
                    }
                    else
                    {
                        jumpsToInstruction[dst.Instruction] = 1;
                    }
                }
            }
            else
            {
                var dst = instruction.Operand as CilInstructionLabel;

                if (jumpsToInstruction.ContainsKey(dst.Instruction))
                {
                    jumpsToInstruction[dst.Instruction]++;
                }
                else
                {
                    jumpsToInstruction[dst.Instruction] = 1;
                }
            }
        }
    }
}

void ComputeJumpsToInstructions(CilInstructionCollection instructions)
{
    foreach (var instruction in instructions)
    {
        if (instruction.IsBranch())
        {
            if (instruction.OpCode == CilOpCodes.Switch)
            {
                var dstList = instruction.Operand as List<ICilLabel>;

                foreach (var dst in dstList.Cast<CilInstructionLabel>())
                {
                    if (jumpsToInstruction.ContainsKey(dst.Instruction))
                    {
                        jumpsToInstruction[dst.Instruction]++;
                    }
                    else
                    {
                        jumpsToInstruction[dst.Instruction] = 1;
                    }
                }
            }
            else
            {
                var dst = instruction.Operand as CilInstructionLabel;

                if (jumpsToInstruction.ContainsKey(dst.Instruction))
                {
                    jumpsToInstruction[dst.Instruction]++;
                }
                else
                {
                    jumpsToInstruction[dst.Instruction] = 1;
                }
            }
        }
    }
}

and this is where it is being read

Block MergeBlocksInternal(Block main, Block merged, List<Block> blocks, HashSet<Block> mergedBlocks)
{
    mergedBlocks.Add(main);

    if (merged == null) // end of block chain
        return main;

    if (mergedBlocks.Contains(merged))
        return main;

    var jumpInstruction = main.instructions.Last();

    if (jumpInstruction.OpCode == CilOpCodes.Br)
    {
        var dst = jumpInstruction.Operand as CilInstructionLabel;
        var dstInstruction = dst.Instruction;

                // vvvvvvvvvvvvv this is where it throws vvvvvvvvvvvvvv
        //if (jumpsToInstruction[dstInstruction] != 1) // this for some reason it doenst work?? it should!
        if (jumpsToInstruction.First(x => x.Key == dstInstruction).Value != 1) // this is a workaround
        {
            return main;
        }

        var destinationBlock = instruction2block[dstInstruction];

        if (dstInstruction != destinationBlock.instructions.First()) // only merge blocks if they link with each other (jumps in the middle of a block does not count)
            return main;

        main.destinationBlock = destinationBlock.destinationBlock;
    }

    main.instructions.RemoveAt(main.instructions.Count - 1);
    main.instructions.AddRange(merged.instructions);

    mergedBlocks.Add(merged);

    return MergeBlocksInternal(main, main.destinationBlock, blocks, mergedBlocks);
}

Block MergeBlocksInternal(Block main, Block merged, List<Block> blocks, HashSet<Block> mergedBlocks)
{
    mergedBlocks.Add(main);

    if (merged == null) // end of block chain
        return main;

    if (mergedBlocks.Contains(merged))
        return main;

    var jumpInstruction = main.instructions.Last();

    if (jumpInstruction.OpCode == CilOpCodes.Br)
    {
        var dst = jumpInstruction.Operand as CilInstructionLabel;
        var dstInstruction = dst.Instruction;

                // vvvvvvvvvvvvv this is where it throws vvvvvvvvvvvvvv
        //if (jumpsToInstruction[dstInstruction] != 1) // this for some reason it doenst work?? it should!
        if (jumpsToInstruction.First(x => x.Key == dstInstruction).Value != 1) // this is a workaround
        {
            return main;
        }

        var destinationBlock = instruction2block[dstInstruction];

        if (dstInstruction != destinationBlock.instructions.First()) // only merge blocks if they link with each other (jumps in the middle of a block does not count)
            return main;

        main.destinationBlock = destinationBlock.destinationBlock;
    }

    main.instructions.RemoveAt(main.instructions.Count - 1);
    main.instructions.AddRange(merged.instructions);

    mergedBlocks.Add(merged);

    return MergeBlocksInternal(main, main.destinationBlock, blocks, mergedBlocks);
}

The call of the 2nd function is quite complex so i cant really put it here, but at the core its basically itterating a List with CilInstruction items

Arthus•11mo ago

Without debbugging will be hard to find. This is what ContainsKey will execute:

//some parsing and code for ValueTypes comparison
 Debug.Assert(comparer is not null);
                    uint hashCode = (uint)comparer.GetHashCode(key);
                    int i = GetBucket(hashCode);
                    Entry[]? entries = _entries;
                    uint collisionCount = 0;
                    i--; // Value in _buckets is 1-based; subtract 1 from i. We do it here so it fuses with the following conditional.
                    do
                    {
                        // Should be a while loop https://github.com/dotnet/runtime/issues/9422
                        // Test in if to drop range check for following array access
                        if ((uint)i >= (uint)entries.Length)
                        {
                            goto ReturnNotFound;
                        }

                        entry = ref entries[i];
                        if (entry.hashCode == hashCode && comparer.Equals(entry.key, key))
                        {
                            goto ReturnFound;
                        }

                        i = entry.next;

                        collisionCount++;
                    } while (collisionCount <= (uint)entries.Length);

                    // The chain of entries forms a loop; which means a concurrent update has happened.
                    // Break out of the loop and throw, rather than looping forever.
                    goto ConcurrentOperation;

//some parsing and code for ValueTypes comparison
 Debug.Assert(comparer is not null);
                    uint hashCode = (uint)comparer.GetHashCode(key);
                    int i = GetBucket(hashCode);
                    Entry[]? entries = _entries;
                    uint collisionCount = 0;
                    i--; // Value in _buckets is 1-based; subtract 1 from i. We do it here so it fuses with the following conditional.
                    do
                    {
                        // Should be a while loop https://github.com/dotnet/runtime/issues/9422
                        // Test in if to drop range check for following array access
                        if ((uint)i >= (uint)entries.Length)
                        {
                            goto ReturnNotFound;
                        }

                        entry = ref entries[i];
                        if (entry.hashCode == hashCode && comparer.Equals(entry.key, key))
                        {
                            goto ReturnFound;
                        }

                        i = entry.next;

                        collisionCount++;
                    } while (collisionCount <= (uint)entries.Length);

                    // The chain of entries forms a loop; which means a concurrent update has happened.
                    // Break out of the loop and throw, rather than looping forever.
                    goto ConcurrentOperation;

Looking at you code and so far seems to be that the issue is on runtime so I can't go any further without debugging. I will sugest write a test and reproduce it If the Tkey in your case CilInstruction has an implemented IEqualityComparer, I understood you toldme they have a custom one, it will use the customComparer (which I understand it works properly)

turnerOP•11mo ago

i guess ill just use the wanky workaround, its not performance critical so its ok

Gaming

Programming

Dictionary cant find via ContainsKey but it does exist