为什么这个方法会导致无限循环？

Question

我的一位同事向我提出了有关导致无限循环的方法的问题。实际的代码有点太复杂了post这里，但本质上问题归结为：

private IEnumerable<int> GoNuts(IEnumerable<int> items)
{
    items = items.Select(item => items.First(i => i == item));
    return items;
}

这应该（您会认为）只是创建列表副本的一种非常低效的方法。我称它为：

var foo = GoNuts(new[]{1,2,3,4,5,6});

结果是无限循环。奇怪。

我认为修改参数在风格上是一件坏事，所以我稍微更改了代码：

var foo = items.Select(item => items.First(i => i == item));
return foo;

成功了。即程序完成；也不例外。

更多实验表明这也有效：

items = items.Select(item => items.First(i => i == item)).ToList();
return items;

和简单的一样

return items.Select(item => .....);

很好奇。

很明显，问题与重新分配参数有关，但前提是评估被推迟到该语句之外。如果我添加 ToList() 它会起作用。

我对出了什么问题有一个笼统的、模糊的想法。看起来 Select 正在迭代它自己的输出。这本身有点奇怪，因为通常 IEnumerable 会在它正在迭代的集合发生变化时抛出。

我不明白的是为什么重新分配参数会导致无限循环，因为我不太熟悉这些东西的内部结构。

有没有懂内幕的人愿意解释一下为什么会出现死循环？

Answer 1

It looks like the Select is iterating over its own output

你是对的。您正在返回一个迭代自身的 query。

关键是您在 lambda 中引用 items 。 items 引用在查询迭代之前不会被解析 ("closed over")，此时 items 现在引用查询而不是源 collection。那是 self-reference 发生的地方。

想象一副纸牌，前面有一个标记为 items 的牌子。现在想象一个人站在一副牌旁边，他的任务是迭代 collection 称为 items。但随后你将牌子从甲板上移到 man 上。当你向那个人要第一个 "item" 时 - 他寻找标记为 "items" 的 collection - 现在就是他了！所以他问自己第一项，也就是循环引用发生的地方。

当您将结果分配给 new 变量时，您就会有一个迭代 different collection 的查询，因此不会导致无限循环。

当您调用 ToList 时，您将查询合并为一个新的 collection，并且不会出现无限循环。

其他会破坏循环引用的东西：

通过调用 ToList
在 lambda

正在将 items 分配给另一个变量并在 lambda 中引用 that。

Answer 2

回答这个问题的关键是延迟执行。当你这样做时

items = items.Select(item => items.First(i => i == item));

您不是迭代传递给方法的 items 数组。相反，您为它分配一个新的 IEnumerable<int>，它会引用自己，并且仅在调用者开始枚举结果时才开始迭代。

这就是为什么您的所有其他修复程序都解决了这个问题：您需要做的就是停止将 IEnumerable<int> 反馈给自身：

使用 var foo 通过使用不同的变量打破自引用，
使用 return items.Select... 通过完全不使用中间变量来破坏自引用，
使用 ToList() 通过避免延迟执行来打破自引用：到 items 被重新分配时，旧的 items 已经被迭代，所以你最终得到一个普通内存 List<int>.

But if it's feeding on itself, how does it get anything at all?

没错，它没有得到任何东西！当您尝试迭代 items 并要求它处理第一项时，延迟序列会要求提供给它的序列处理第一项，这意味着该序列正在要求自己处理第一项。在这一点上，它是 turtles all the way down，因为为了 return 处理序列的第一个项目必须首先从自身获取第一个要处理的项目。

Answer 3

在研究了给出的两个答案并仔细研究之后，我想出了一个能更好地说明问题的小程序。

    private int GetFirst(IEnumerable<int> items, int foo)
    {
        Console.WriteLine("GetFirst {0}", foo);
        var rslt = items.First(i => i == foo);
        Console.WriteLine("GetFirst returns {0}", rslt);
        return rslt;
    }

    private IEnumerable<int> GoNuts(IEnumerable<int> items)
    {
        items = items.Select(item =>
        {
            Console.WriteLine("Select item = {0}", item);
            return GetFirst(items, item);
        });
        return items;
    }

如果你调用它：

var newList = GoNuts(new[]{1, 2, 3, 4, 5, 6});

你会反复得到这个输出，直到你最终得到 WhosebugException。

Select item = 1
GetFirst 1
Select item = 1
GetFirst 1
Select item = 1
GetFirst 1
...

这显示的正是 dasblinkenlight 在其更新后的答案中明确指出的内容：查询进入无限循环以尝试获取第一项。

让我们用稍微不同的方式写GoNuts：

    private IEnumerable<int> GoNuts(IEnumerable<int> items)
    {
        var originalItems = items;
        items = items.Select(item =>
        {
            Console.WriteLine("Select item = {0}", item);
            return GetFirst(originalItems, item);
        });
        return items;
    }

如果你运行那，它就成功了。为什么？因为在这种情况下，很明显对 GetFirst 的调用正在传递对传递给该方法的原始项的引用。在第一种情况下，GetFirst 正在传递对 new items 集合的引用，但尚未实现。反过来，GetFirst 表示，"Hey, I need to enumerate this collection." 从而开始第一个最终导致 WhosebugException.

的递归调用

有趣的是，当我说它正在消耗自己的输出时，我是对的而是错误的。正如我所料，Select 正在消耗原始输入。 First 正在尝试消耗输出。

在这里可以学到很多东西。对我来说，最重要的是"don't modify the value of input parameters."

感谢 dasblinkenlight、D Stanley 和 Lucas Trzesniewski 的帮助。

为什么这个方法会导致无限循环？

Why does this method result in an infinite loop?

c#

linq

stack-overflow

infinite-loop