Iterating over IEnumerable using foreach skips some elements

Question

I've faced with difference in behavior between iterating over enumerable and over enumerable.ToList().

public static void Kill(Point location)
{
    Wound(location);
    foreach(var point in GetShipPointsAndTheirNeighbors(location).ToList())
    {
        CellsWithShips[point.X, point.Y] = false;
    }
}

/// <summary>
/// This version does not work for strange reasons, it just skips a half of points. See TestKill_DoesNotWork_1 test case
/// </summary>
/// <param name="location"></param>
public static void Kill_DoesNotWork(Point location)
{
    Wound(location);
    foreach(var point in GetShipPointsAndTheirNeighbors(location))
    {
        CellsWithShips[point.X, point.Y] = false;
    }
}

As you can see, the only difference between these methods is that the first one iterates over List of points, while the Kill_DoesNotWork iterates over IEnumerable<Point>. However, the last method sometimes skips elements (Ideone example).

There is full code (I am sorry for 170 lines of code, but I cannot compress it more)

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace SampleAi
{
    [DebuggerDisplay("Pont({X}, {Y})")]
    public class Point
    {
        #region Constructors

        public Point(int x, int y)
        {
            X = x;
            Y = y;
        } 

        #endregion // Constructors

        #region Properties

        public int X
        {
            get;
            private set;
        }

        public int Y
        {
            get;
            private set;
        }

        #endregion // Properties

        #region Methods

        public Point Add(Point point)
        {
            return new Point(X + point.X, Y + point.Y);
        }

        #endregion // Methods

        #region Overrides of Object

        /// <summary>
        /// Returns a string that represents the current object.
        /// </summary>
        /// <returns>
        /// A string that represents the current object.
        /// </returns>
        public override string ToString()
        {
            return string.Format("Point({0}, {1})", X, Y);
        }

        #endregion
    }

    public static class Map
    {
        #region Properties

        private static bool[,] CellsWithShips
        {
            get;
            set;
        }

        #endregion // Properties

        #region Methods

        public static IEnumerable<Point> GetAllShipPoints()
        {
            return Enumerable.Range(0, CellsWithShips.GetLength(0))
                             .SelectMany(x => Enumerable.Range(0, CellsWithShips.GetLength(1)).Select(y => new Point(x, y)))
                             .Where(p => CellsWithShips[p.X, p.Y]);
        }

        public static void Init(int width, int height)
        {
            CellsWithShips = new bool[width, height];
        }

        public static void Wound(Point location)
        {
            CellsWithShips[location.X, location.Y] = true;
        }

        public static void Kill(Point location)
        {
            Wound(location);
            foreach(var point in GetShipPointsAndTheirNeighbors(location).ToList())
            {
                CellsWithShips[point.X, point.Y] = false;
            }
        }

        /// <summary>
        /// This version does not work for strange reasons, it just skips a half of points. See TestKill_DoesNotWork_1 test case
        /// </summary>
        /// <param name="location"></param>
        public static void Kill_DoesNotWork(Point location)
        {
            Wound(location);
            foreach(var point in GetShipPointsAndTheirNeighbors(location))
            {
                CellsWithShips[point.X, point.Y] = false;
            }
        }

        private static IEnumerable<Point> GetShipPointsAndTheirNeighbors(Point location)
        {
            return GetShipPoints(location).SelectMany(Near);
        }

        private static IEnumerable<Point> Near(Point location)
        {
            return new[]
            {
                location.Add(new Point(0, -1)),
                location.Add(new Point(0, 0))
            };
        }

        private static IEnumerable<Point> GetShipPoints(Point location)
        {
            var beforePoint = new[]
            {
                location,
                location.Add(new Point(0, -1)),
                location.Add(new Point(0, -2)),
                location.Add(new Point(0, -3))
            };
            return beforePoint.TakeWhile(p => CellsWithShips[p.X, p.Y]);
        }

        #endregion // Methods
    }

    public static class Program
    {
        private static void LoadMap()
        {
            Map.Init(20, 20);

            Map.Wound(new Point(1, 4));
            Map.Wound(new Point(1, 5));
            Map.Wound(new Point(1, 6));
        }

        private static int TestKill()
        {
            LoadMap();
            Map.Kill(new Point(1, 7));
            return Map.GetAllShipPoints().Count();
        }

        private static int TestKillDoesNotWork()
        {
            LoadMap();
            Map.Kill_DoesNotWork(new Point(1, 7));
            return Map.GetAllShipPoints().Count();
        }

        private static void Main()
        {
            Console.WriteLine("Test kill: {0}", TestKill());
            Console.WriteLine("Test kill (does not work): {0}", TestKillDoesNotWork());
        }
    }
}

Since this is compressed code, most of functions does not exactly what they should. If you want to cut it more, you could use this gist for sharing your code (gist with unit tests).

I am using MSVS 2013 (12.0.30110.00 Update 1) with .NET Framework v4.5.51650

Answer 1

The call to ToList() will materialise the resulting selection of items as it looked at that point in time. Iterating over an IEnumerable will evaluate the expressions given for each item and yield them, one by one, and thus reality can have changed between iterations. In fact, it's probably very likely that this happens since you change the properties of items between iterations.

In the body of your iteration, you set

CellsWithShips[point.X, point.Y] = false;

In the selection of your method, you query for

things.Where(p => CellsWithShips[p.X, p.Y]);

This means that the inherently dynamic result of such a query will change, since you've set some of those results to false. But only because it evaluates every item, one by one, as needed. This is called deferred execution and is most often used to optimize large queries or long-running, dynamically sized operations.