Linq orderby clause appears to be duplicating and losing objects

Question

I'm writing a Windows Forms program. I'm fairly new to linq. I want to order a list of objects in memory. The objects are of class Ctrl (and represent controls on the screen). They have properties which include: CtrlID, Name, X, Y, TabIndex. TabIndex may be zero for a lot of the controls, so I want to order them by TabIndex, Y, X and then run through them setting the TabIndex from one, incrementing, so it is contiguous.

The code I am using is this:

            int i;
            Ctrl oCtrl = null;

            Debug.WriteLine("Before");
                for (i = 0; i < _ctrls.Count; i++)
                {
                    oCtrl = _ctrls[i];
                    Debug.WriteLine(string.Format("{0},ID:{1}: Name:{2}, TabIndex:{3}, X:{4}, Y:{5} ", i.ToString(), oCtrl.CtrlID, oCtrl.Name, oCtrl.TabIndex.ToString(), oCtrl.X, oCtrl.Y));
                }

                var ctrls = from ctrl in _ctrls.Items 
                            orderby ctrl.TabIndex, ctrl.Y, ctrl.X 
                            select ctrl;

                Debug.WriteLine("After");
                for (i = 0; i < ctrls.Count(); i++)
                {
                    oCtrl = ctrls.ElementAt(i);
                    Debug.WriteLine(string.Format("{0},ID:{1}: Name:{2}, TabIndex:{3}, X:{4}, Y:{5} ", i.ToString(), oCtrl.CtrlID, oCtrl.Name, oCtrl.TabIndex.ToString(), oCtrl.X, oCtrl.Y));
                    oCtrl.TabIndex = i + 1; // cos they're one-based
                }

And the results I get in the Output window are these:

0,ID:125: Name:cmd, TabIndex:0, X:124, Y:12 
1,ID:126: Name:chk, TabIndex:0, X:124, Y:36 
2,ID:127: Name:db, TabIndex:0, X:124, Y:60 
3,ID:128: Name:LABEL1, TabIndex:0, X:8, Y:64 
4,ID:129: Name:LABEL2, TabIndex:0, X:8, Y:88 
5,ID:130: Name:nf, TabIndex:0, X:124, Y:84 
6,ID:131: Name:ni, TabIndex:0, X:124, Y:108 
7,ID:132: Name:LABEL3, TabIndex:0, X:8, Y:112 
8,ID:133: Name:sc, TabIndex:0, X:124, Y:132 
9,ID:134: Name:LABEL4, TabIndex:0, X:8, Y:136 
10,ID:135: Name:sv, TabIndex:0, X:124, Y:156 
11,ID:136: Name:LABEL5, TabIndex:0, X:8, Y:160 
12,ID:137: Name:LABEL6, TabIndex:0, X:8, Y:292 
13,ID:138: Name:txt, TabIndex:0, X:124, Y:288 
14,ID:139: Name:LABEL7, TabIndex:0, X:8, Y:40 
15,ID:140: Name:LABEL8, TabIndex:0, X:8, Y:16 
After
0,ID:125: Name:cmd, TabIndex:0, X:124, Y:12 
1,ID:126: Name:chk, TabIndex:0, X:124, Y:36 
2,ID:127: Name:db, TabIndex:0, X:124, Y:60 
3,ID:130: Name:nf, TabIndex:0, X:124, Y:84 
4,ID:131: Name:ni, TabIndex:0, X:124, Y:108 
5,ID:133: Name:sc, TabIndex:0, X:124, Y:132 
6,ID:135: Name:sv, TabIndex:0, X:124, Y:156 
7,ID:138: Name:txt, TabIndex:0, X:124, Y:288 
8,ID:125: Name:cmd, TabIndex:1, X:124, Y:12 
9,ID:127: Name:db, TabIndex:3, X:124, Y:60 
10,ID:131: Name:ni, TabIndex:5, X:124, Y:108 
11,ID:135: Name:sv, TabIndex:7, X:124, Y:156 
12,ID:125: Name:cmd, TabIndex:9, X:124, Y:12 
13,ID:131: Name:ni, TabIndex:11, X:124, Y:108 
14,ID:125: Name:cmd, TabIndex:13, X:124, Y:12 
15,ID:125: Name:cmd, TabIndex:15, X:124, Y:12

All the controls named "LABEL..." are missing, and some of the rest are duplicated. The values where TabIndex showing as > 0 is due to the fact that I am setting its value after printing the output, but because some of the objects are referenced twice, the new value is showing the second time round. If I comment out the orderby clause so it is a straight select, I get the data back in the order it is currently in, without duplicates or items missing.

So:

why am I missing objects?
why have I got duplicate objects?
how do I get orderby to do what I am expecting?

Thanks for any help provided.

First of: don´t make an indexed based access through an `IEnumerable`, but just a `foreach`. Alternativly call `ToList` on your query-result. Second: did you verify your input-collection does **not** have those duplicates? — MakePeaceGreatAgain, Jan 29 '21 at 09:30
The _shortest_ fix is after assigning to `ctrls` add a line of `ctrls = ctrls.ToList();`. The key bit to understand here is that you are repeatedly _doing_ the `OrderBy`. @HimBromBeere's suggestion to use foreach rather than for is likely the _better_ solution. https://stackoverflow.com/questions/4830039/index-in-the-select-projection will show you how to get the index (i) with a `foreach`. — mjwills, Jan 29 '21 at 09:35
Thanks both. Could you explain what you mean by "repeatedly doing the OrderBy"? Does the orderby keep operating after the ```var ctrls = from ctrl in _ctrls.Items...``` statement? i.e. as I change the values of TabIndex? — Mark Roworth, Jan 29 '21 at 09:38
Well, the querty does not return a **collection**, but just an **iterator** to it. Have a look at https://learn.microsoft.com/en-us/dotnet/standard/linq/deferred-execution-lazy-evaluation to understand the difference. In short doing something on an **iterator** multiple times (in your case calling `ElementAt`) will execute the underlying **query** multiple times. — MakePeaceGreatAgain, Jan 29 '21 at 09:47
Ah thank you. I have a better understanding now. It seems strange with an orderby clause that you would lazy evaulate it though, as you need to have ordered all the elements to work out which one comes first. You help much appreciated. — Mark Roworth, Jan 29 '21 at 10:00
`It seems strange with an orderby clause that you would lazy evaulate it though, as you need to have ordered all the elements to work out which one comes first.` It is key to understand that your LINQ query is more like a _recipe_ than a _meal_. You've told it how to order it, but _haven't actually done the ordering_. Imagine you ordered your children by name. You ask for the 1st one, then _change their name_. Then you ask for the 2nd one - but, alas, in the meantime they re-ordered to reflect their new name. So you may get the "1st" one again. `ToList` forces "get in order, and stay there". — mjwills, Jan 29 '21 at 10:04
@mjwills That´s an awesome explanation of lazy evaluation. In particular the "get in order and stay there"-part. — MakePeaceGreatAgain, Jan 29 '21 at 10:08
Thanks @HimBromBeere. Physical examples help me visualise stuff better. — mjwills, Jan 29 '21 at 10:17

Alexandru Clonțea · Answer 1 · 2021-01-29T12:45:59.280

I was wrong in my original assessment, I was thinking along the lines of the very valid points of mjwills. However, even if the solution I had pointed to would work, the root cause for this particular case does not seem to be the mutation itself.

The root cause for this particular issue you're running into is the use of ElementAt (https://referencesource.microsoft.com/#system.core/system/linq/Enumerable.cs,1231)

public static TSource ElementAt<TSource>(this IEnumerable<TSource> source, int index) {
if (source == null) throw Error.ArgumentNull("source");
        IList<TSource> list = source as IList<TSource>;
        if (list != null) return list[index];
        if (index < 0) throw Error.ArgumentOutOfRange("index");
        using (IEnumerator<TSource> e = source.GetEnumerator()) {
            while (true) {
                if (!e.MoveNext()) throw Error.ArgumentOutOfRange("index");
                if (index == 0) return e.Current;
                index--;
            }
        }
    }

It seems that if the source is not an IList<TSource>, a new IEnumerator<TSource> is generated each time and an iteration is done until the element is reached. I believed that you would have used indexing if it was. That seems to be why the ordering changed on you. (self promoting a good read on IList vs IEnumerable: https://stackoverflow.com/a/52450636/8695782)

On top of that, this way of accessing elements highly inefficient, even if unnoticeable in this case. On top of it being inefficient, you can run into other troubles as well in the case of non-rewindable IEnumerables (i.e. a non-list-backed perpetual yielder).

If you change your loop to:

Console.WriteLine("After");
var index = 1;
foreach (var ctrl in _ctrls)
{
    oCtrl = ctrl;
    oCtrl.TabIndex = index++;
    Console.WriteLine(string.Format("Name:{0}, TabIndex:{1}", oCtrl.Name, oCtrl.TabIndex.ToString()));
}

Then your code should work as well since we only create one IEnumerator<TSource> implicitly when writing the foreach line.

[original assessment - (partly) wrong]

As mjwills has beautifully pointed out in his comment, your LINQ query is more of a recipe than a meal, so it may re-evaluate while you iterate it. Mutating objects while iterating any kind of IEnumerable/IQueryable is usually a recipe for disaster in the long run. That is the reason you get duplicates/missing items.

3. In your specific case, changing

orderby ctrl.TabIndex, ctrl.Y, ctrl.X

to

orderby ctrl.Y, ctrl.X

will achieve what I think the desired result is since TabIndex is something that you are trying to compute and update.

From what I can tell in the code, they all start out as TabIndex = 0. So in this particular case, having the ordering just by X and Y means that changing TabIndex would not affect the ordering.

`Mutating objects while iterating any kind of IEnumerable/IQueryable` Technically he is not mutating them _while_ iterating - but I agree with most of the rest of your argument. — mjwills, Jan 29 '21 at 21:56
@mjwillis, Thanks for pointing this out! I will have to update/refine my answer after I get some sleep. You are entirely right, the "backing" list itself would have to mutate as in adding or removing items to run into what I was hinting at. I don't know what drove me to make that claim. — Alexandru Clonțea, Jan 30 '21 at 01:34

Linq orderby clause appears to be duplicating and losing objects

1 Answers1