Runtime: ImmutableList<T>.Builder.RemoveAll removes elements for which the Predicate is false

[cdmihai]

Repro: \\fsu\shares\MsEng\MSBuild\micodoba\ImmutableListBuilderRepro.zip

1. open a VS 2017 terminal and navigate to repro dir
2. terminal: start .\msbuild\src\MSBuild.sln
3. VS: set breakpoint in Microsoft.Build.Evaluation.LazyItemEvaluator.RemoveOperation.SaveItems at line 34 (with contents listBuilder.RemoveAll(itemData => items.Contains(itemData.Item));)
4. terminal: set MSBUILDDEBUGONSTART=2
5. terminal: .\msbuild\bin\Bootstrap\MSBuild\15.0\Bin\MSBuild.exe .\GlobbingProblem\GlobbingProblem\GlobbingProblem.csproj
6. VS: attach to msbuild process ID and hit any key in terminal
7. VS: breakpoint is hit and the following state exists:
   
   
   
   • items has 5 elements in it:
   
   

+       [0] "Compile"="C:\\Users\\micodoba\\.nuget\\packages\\nservicebus.acceptancetests.sources\\6.3.0-alpha0113\\contentFiles\\cs\\any\\NSB.AcceptanceTests\\Audit\\When_audit_is_overridden_in_code.cs" #DirectMetadata=5)  Microsoft.Build.Execution.ProjectItemInstance
+       [1] "Compile"="C:\\Users\\micodoba\\.nuget\\packages\\nservicebus.acceptancetests.sources\\6.3.0-alpha0113\\contentFiles\\cs\\any\\NSB.AcceptanceTests\\Audit\\When_a_replymessage_is_audited.cs" #DirectMetadata=5)    Microsoft.Build.Execution.ProjectItemInstance
+       [2] "Compile"="C:\\Users\\micodoba\\.nuget\\packages\\nservicebus.acceptancetests.sources\\6.3.0-alpha0113\\contentFiles\\cs\\any\\NSB.AcceptanceTests\\Audit\\When_auditing_message_with_TimeToBeReceived.cs" #DirectMetadata=5)   Microsoft.Build.Execution.ProjectItemInstance
+       [3] "Compile"="C:\\Users\\micodoba\\.nuget\\packages\\nservicebus.acceptancetests.sources\\6.3.0-alpha0113\\contentFiles\\cs\\any\\NSB.AcceptanceTests\\Audit\\When_a_message_is_audited.cs" #DirectMetadata=5) Microsoft.Build.Execution.ProjectItemInstance
+       [4] "Compile"="C:\\Users\\micodoba\\.nuget\\packages\\nservicebus.acceptancetests.sources\\6.3.0-alpha0113\\contentFiles\\cs\\any\\NSB.AcceptanceTests\\Audit\\When_auditing.cs" #DirectMetadata=5) Microsoft.Build.Execution.ProjectItemInstance

• listBuilder has 190 items in it
  
  
  
  1. step over line 34 so the list builder performs the RemoveAll.
  
  

Expected: 5 elements are removed, the ones from items.
Actual: 6 elements are removed. The unexpected removed element is an item with the value: C:\Users\micodoba\.nuget\packages\nservicebus.acceptancetests.sources\6.3.0-alpha0113\contentFiles\cs\any\NSB.AcceptanceTests\ConfigureEndpointLearningTransport.cs.

If you replace the RemoveAll with Remove, then only the expected items are removed.

MSBuild issue: https://github.com/Microsoft/msbuild/issues/2069

[danmosemsft]

Thanks @cdmihai . It sounds like this could be reproduced in just a few lines - any chance you could make such a repro?

[cdmihai]

I managed to reduce it to a template console project.

Elements before removal: 190
Removing 5 elements
Elements after removal: 184

Zipped project:
RemoveAll.zip

[cdmihai]

Smaller repro:

```c#
using System;
using System.Collections.Immutable;
using Enumerable = System.Linq.Enumerable;

namespace RemoveAll
{
class Program
{
static void Main(string[] args)
{
TestWith(6, 5);
TestWith(5, 5);
TestWith(190, 5, 1);

        Console.ReadKey();
    }

    private static void TestWith(int totalItems, int itemsToRemove, int removeOffset = 0)
    {
        Console.WriteLine($"\n============={totalItems}-{itemsToRemove}===============\n");
        var builder = ImmutableList.CreateBuilder<int>();

        foreach (var element in Enumerable.Range(0, totalItems))
        {
            builder.Add(element);
        }

        var elementsToRemove = Enumerable.Range(removeOffset, itemsToRemove).ToImmutableHashSet();

        Console.WriteLine($"{builder.Count} elements before removal:\n{string.Join(",", builder)}");

        Console.WriteLine($"\n{elementsToRemove.Count} elements to remove:\n{string.Join(",", elementsToRemove)}\n");
        builder.RemoveAll(element => Contains(elementsToRemove, element));

        Console.WriteLine($"\n{builder.Count} elements after removal:\n{string.Join(",", builder)}");
    }

    private static bool Contains(ImmutableHashSet<int> elementsToRemove, int element)
    {
        var answer =  elementsToRemove.Contains(element);

        Console.WriteLine($"\t{string.Join(",", elementsToRemove)} is asked if it contains {element}");

        return answer;
    }
}

}

Produces:

=============6-5===============

6 elements before removal:
0,1,2,3,4,5

5 elements to remove:
0,1,2,3,4

    0,1,2,3,4 is asked if it contains 0
    0,1,2,3,4 is asked if it contains 1
    0,1,2,3,4 is asked if it contains 2
    0,1,2,3,4 is asked if it contains 3

2 elements after removal:
4,5

=============5-5===============

5 elements before removal:
0,1,2,3,4

5 elements to remove:
0,1,2,3,4

    0,1,2,3,4 is asked if it contains 0
    0,1,2,3,4 is asked if it contains 1
    0,1,2,3,4 is asked if it contains 2

2 elements after removal:
3,4

=============190-5===============

190 elements before removal:
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189

5 elements to remove:
1,2,3,4,5

    1,2,3,4,5 is asked if it contains 0
    1,2,3,4,5 is asked if it contains 1
    1,2,3,4,5 is asked if it contains 2
    1,2,3,4,5 is asked if it contains 3
    1,2,3,4,5 is asked if it contains 4
    1,2,3,4,5 is asked if it contains 5    X
    1,2,3,4,5 is asked if it contains 6
    1,2,3,4,5 is asked if it contains 5    X
    1,2,3,4,5 is asked if it contains 0    X
    1,2,3,4,5 is asked if it contains 6    X
    1,2,3,4,5 is asked if it contains 7
    1,2,3,4,5 is asked if it contains 9
    1,2,3,4,5 is asked if it contains 10
    1,2,3,4,5 is asked if it contains 11
    1,2,3,4,5 is asked if it contains 12
    1,2,3,4,5 is asked if it contains 13
    1,2,3,4,5 is asked if it contains 14
    1,2,3,4,5 is asked if it contains 15
    1,2,3,4,5 is asked if it contains 16
    1,2,3,4,5 is asked if it contains 17
    1,2,3,4,5 is asked if it contains 18
    1,2,3,4,5 is asked if it contains 19
    1,2,3,4,5 is asked if it contains 20
    1,2,3,4,5 is asked if it contains 21
    1,2,3,4,5 is asked if it contains 22
    1,2,3,4,5 is asked if it contains 23
    1,2,3,4,5 is asked if it contains 24
    1,2,3,4,5 is asked if it contains 25
    1,2,3,4,5 is asked if it contains 26
    1,2,3,4,5 is asked if it contains 27
    1,2,3,4,5 is asked if it contains 28
    1,2,3,4,5 is asked if it contains 29
    1,2,3,4,5 is asked if it contains 30
    1,2,3,4,5 is asked if it contains 31
    1,2,3,4,5 is asked if it contains 32
    1,2,3,4,5 is asked if it contains 33
    1,2,3,4,5 is asked if it contains 34
    1,2,3,4,5 is asked if it contains 35
    1,2,3,4,5 is asked if it contains 36
    1,2,3,4,5 is asked if it contains 37
    1,2,3,4,5 is asked if it contains 38
    1,2,3,4,5 is asked if it contains 39
    1,2,3,4,5 is asked if it contains 40
    1,2,3,4,5 is asked if it contains 41
    1,2,3,4,5 is asked if it contains 42
    1,2,3,4,5 is asked if it contains 43
    1,2,3,4,5 is asked if it contains 44
    1,2,3,4,5 is asked if it contains 45
    1,2,3,4,5 is asked if it contains 46
    1,2,3,4,5 is asked if it contains 47
    1,2,3,4,5 is asked if it contains 48
    1,2,3,4,5 is asked if it contains 49
    1,2,3,4,5 is asked if it contains 50
    1,2,3,4,5 is asked if it contains 51
    1,2,3,4,5 is asked if it contains 52
    1,2,3,4,5 is asked if it contains 53
    1,2,3,4,5 is asked if it contains 54
    1,2,3,4,5 is asked if it contains 55
    1,2,3,4,5 is asked if it contains 56
    1,2,3,4,5 is asked if it contains 57
    1,2,3,4,5 is asked if it contains 58
    1,2,3,4,5 is asked if it contains 59
    1,2,3,4,5 is asked if it contains 60
    1,2,3,4,5 is asked if it contains 61
    1,2,3,4,5 is asked if it contains 62
    1,2,3,4,5 is asked if it contains 63
    1,2,3,4,5 is asked if it contains 64
    1,2,3,4,5 is asked if it contains 65
    1,2,3,4,5 is asked if it contains 66
    1,2,3,4,5 is asked if it contains 67
    1,2,3,4,5 is asked if it contains 68
    1,2,3,4,5 is asked if it contains 69
    1,2,3,4,5 is asked if it contains 70
    1,2,3,4,5 is asked if it contains 71
    1,2,3,4,5 is asked if it contains 72
    1,2,3,4,5 is asked if it contains 73
    1,2,3,4,5 is asked if it contains 74
    1,2,3,4,5 is asked if it contains 75
    1,2,3,4,5 is asked if it contains 76
    1,2,3,4,5 is asked if it contains 77
    1,2,3,4,5 is asked if it contains 78
    1,2,3,4,5 is asked if it contains 79
    1,2,3,4,5 is asked if it contains 80
    1,2,3,4,5 is asked if it contains 81
    1,2,3,4,5 is asked if it contains 82
    1,2,3,4,5 is asked if it contains 83
    1,2,3,4,5 is asked if it contains 84
    1,2,3,4,5 is asked if it contains 85
    1,2,3,4,5 is asked if it contains 86
    1,2,3,4,5 is asked if it contains 87
    1,2,3,4,5 is asked if it contains 88
    1,2,3,4,5 is asked if it contains 89
    1,2,3,4,5 is asked if it contains 90
    1,2,3,4,5 is asked if it contains 91
    1,2,3,4,5 is asked if it contains 92
    1,2,3,4,5 is asked if it contains 93
    1,2,3,4,5 is asked if it contains 94
    1,2,3,4,5 is asked if it contains 95
    1,2,3,4,5 is asked if it contains 96
    1,2,3,4,5 is asked if it contains 97
    1,2,3,4,5 is asked if it contains 98
    1,2,3,4,5 is asked if it contains 99
    1,2,3,4,5 is asked if it contains 100
    1,2,3,4,5 is asked if it contains 101
    1,2,3,4,5 is asked if it contains 102
    1,2,3,4,5 is asked if it contains 103
    1,2,3,4,5 is asked if it contains 104
    1,2,3,4,5 is asked if it contains 105
    1,2,3,4,5 is asked if it contains 106
    1,2,3,4,5 is asked if it contains 107
    1,2,3,4,5 is asked if it contains 108
    1,2,3,4,5 is asked if it contains 109
    1,2,3,4,5 is asked if it contains 110
    1,2,3,4,5 is asked if it contains 111
    1,2,3,4,5 is asked if it contains 112
    1,2,3,4,5 is asked if it contains 113
    1,2,3,4,5 is asked if it contains 114
    1,2,3,4,5 is asked if it contains 115
    1,2,3,4,5 is asked if it contains 116
    1,2,3,4,5 is asked if it contains 117
    1,2,3,4,5 is asked if it contains 118
    1,2,3,4,5 is asked if it contains 119
    1,2,3,4,5 is asked if it contains 120
    1,2,3,4,5 is asked if it contains 121
    1,2,3,4,5 is asked if it contains 122
    1,2,3,4,5 is asked if it contains 123
    1,2,3,4,5 is asked if it contains 124
    1,2,3,4,5 is asked if it contains 125
    1,2,3,4,5 is asked if it contains 126
    1,2,3,4,5 is asked if it contains 127
    1,2,3,4,5 is asked if it contains 128
    1,2,3,4,5 is asked if it contains 129
    1,2,3,4,5 is asked if it contains 130
    1,2,3,4,5 is asked if it contains 131
    1,2,3,4,5 is asked if it contains 132
    1,2,3,4,5 is asked if it contains 133
    1,2,3,4,5 is asked if it contains 134
    1,2,3,4,5 is asked if it contains 135
    1,2,3,4,5 is asked if it contains 136
    1,2,3,4,5 is asked if it contains 137
    1,2,3,4,5 is asked if it contains 138
    1,2,3,4,5 is asked if it contains 139
    1,2,3,4,5 is asked if it contains 140
    1,2,3,4,5 is asked if it contains 141
    1,2,3,4,5 is asked if it contains 142
    1,2,3,4,5 is asked if it contains 143
    1,2,3,4,5 is asked if it contains 144
    1,2,3,4,5 is asked if it contains 145
    1,2,3,4,5 is asked if it contains 146
    1,2,3,4,5 is asked if it contains 147
    1,2,3,4,5 is asked if it contains 148
    1,2,3,4,5 is asked if it contains 149
    1,2,3,4,5 is asked if it contains 150
    1,2,3,4,5 is asked if it contains 151
    1,2,3,4,5 is asked if it contains 152
    1,2,3,4,5 is asked if it contains 153
    1,2,3,4,5 is asked if it contains 154
    1,2,3,4,5 is asked if it contains 155
    1,2,3,4,5 is asked if it contains 156
    1,2,3,4,5 is asked if it contains 157
    1,2,3,4,5 is asked if it contains 158
    1,2,3,4,5 is asked if it contains 159
    1,2,3,4,5 is asked if it contains 160
    1,2,3,4,5 is asked if it contains 161
    1,2,3,4,5 is asked if it contains 162
    1,2,3,4,5 is asked if it contains 163
    1,2,3,4,5 is asked if it contains 164
    1,2,3,4,5 is asked if it contains 165
    1,2,3,4,5 is asked if it contains 166
    1,2,3,4,5 is asked if it contains 167
    1,2,3,4,5 is asked if it contains 168
    1,2,3,4,5 is asked if it contains 169
    1,2,3,4,5 is asked if it contains 170
    1,2,3,4,5 is asked if it contains 171
    1,2,3,4,5 is asked if it contains 172
    1,2,3,4,5 is asked if it contains 173
    1,2,3,4,5 is asked if it contains 174
    1,2,3,4,5 is asked if it contains 175
    1,2,3,4,5 is asked if it contains 176
    1,2,3,4,5 is asked if it contains 177
    1,2,3,4,5 is asked if it contains 178
    1,2,3,4,5 is asked if it contains 179
    1,2,3,4,5 is asked if it contains 180
    1,2,3,4,5 is asked if it contains 181
    1,2,3,4,5 is asked if it contains 182
    1,2,3,4,5 is asked if it contains 183
    1,2,3,4,5 is asked if it contains 184
    1,2,3,4,5 is asked if it contains 185
    1,2,3,4,5 is asked if it contains 186
    1,2,3,4,5 is asked if it contains 187

184 elements after removal:
0,6,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131,132,133,134,135,136,137,138,139,140,141,142,143,144,145,146,147,148,149,150,151,152,153,154,155,156,157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189
```

[cdmihai]

Smaller test case which removes more items than needed:

=============20-5===============

20 elements before removal:
0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19

5 elements to remove:
1,2,3,4,5

        1,2,3,4,5 is asked if it contains 1
        1,2,3,4,5 is asked if it contains 2
        1,2,3,4,5 is asked if it contains 3
        1,2,3,4,5 is asked if it contains 4
        1,2,3,4,5 is asked if it contains 5
        1,2,3,4,5 is asked if it contains 5

14 elements after removal:
0,6,8,9,10,11,12,13,14,15,16,17,18,19

[danmosemsft]

Awesome thanks @cdmihai !

[safern]

cc: @AArnott

[sharwell]

The root cause of the problem appears to be iteration here over a collection which is changed during the enumeration. Normally this condition results in an exception rather than state corruption, but since the implementation of RemoveAll operates directly on the underlying Node, the version doesn't change until RemoveAll finally returns (setting Root triggers the version increment).

[kellypleahy]

I have a fix for this. Can I get assigned?

[kellypleahy]

BTW, thanks @sharwell for the investigation - your hypothesis was spot on.

[sharwell]

@kellypleahy Even though you aren't "assigned" here on GitHub, since you offered up a solution first our preference is to work with you to get it into a state where it can be merged even if someone were to offer up a more complete solution later. Sometimes it can take time to get people added to the organization where they can be officially assigned issues, so it's more common for someone already working with you to get assigned as the "sponsor" for a new contributor's PR. :smile:

[danmosemsft]

@kellypleahy you should get a collaborator invite mailed. then I can assign issues to you.

[karelz]

@kellypleahy welcome! I didn't expect you to start contributing the next day after .NET Fringe, very nice surprise! ;)