4

我一直在研究基于类的有限随机访问范围。在对其进行一些测试时:

auto myRange = /* construct my range */
static assert (isRandomAccessRange!(typeof(myRange))); // 
static assert (!isInfinite!(typeof(myRange)));         // both pass 
auto preamble = myRange[0..128];
assert( all!"a == 0"(preamble)); // check for all zeros

我在 GDC 4.9.2 中遇到了这个编译错误,关于上面片段中的最后一行:“algorithm.d|4838|error: foreach: cannot make e ref”

错误指向std.algorithm.find(find_if 变体,采用范围和谓词)中的这段代码,它确实引用了每个元素foreach

InputRange find(alias pred, InputRange)(InputRange haystack)
if (isInputRange!InputRange)
{
    alias R = InputRange;
    alias predFun = unaryFun!pred;
    static if (isNarrowString!R)
    {
        ...
    }
    else static if (!isInfinite!R && hasSlicing!R && is(typeof(haystack[cast(size_t)0 .. $])))
    {
        size_t i = 0;
        foreach (ref e; haystack) // <-- needs a ref
        {
            if (predFun(e))
                return haystack[i .. $];
            ++i;
        }
        return haystack[$ .. $];
    }
    else
    {
       ...
    }
}

这很可能发生,因为我提供了一个opApply不提供ref参数的实现(该类也不ref向任何其他成员函数提供返回类型)。

int opApply(int delegate(E) f) {...}
int opApply(int delegate(size_t,E) f) {...}

我可以改变它,但真正困扰我的是,现在范围类符合函数的先决条件,并且foreach迭代仍然应该与它们一起工作。从文档中引用:

结构和类对象的迭代可以用范围来完成。对于foreach,这意味着必须定义以下属性和方法:

特性:

  • .empty 如果没有更多元素,则返回 true
  • .front 返回范围的最左边的元素

方法:

  • .popFront() 将范围的左边缘向右移动一位

所有这些都提供了(否则它不会是随机访问范围),所以它应该使用它们。相反,它可能正在寻找下面描述的替代迭代方法:

如果聚合表达式是结构或类对象,并且范围属性不存在,则 foreach 由特殊opApply成员函数定义,foreach_reverse 行为由特殊opApplyReverse成员函数定义。这些函数具有以下类型:

int opApply(int delegate(ref Type [, ...]) dg);

根据我的解释,不应该寻找。

也 quoting std.algorithm.all,这似乎也不需要迭代引用:

bool all(Range)(Range range) if (isInputRange!Range && is(typeof(unaryFun!pred(range.front))));

当且仅当在输入范围范围内找到的所有值 v 都满足谓词 pred 时返回 true。(至多)对 pred 执行 Ο(range.length) 评估。

那么这是 Phobos 库中的一个错误,std.algorithm.find应该首先按值迭代吗?还是我错过了什么?

4

1 回答 1

1

在一个应该是范围的对象上声明甚至没有意义opApply,因为如果它是一个范围,那么基于范围的函数将用于foreach,而不是opApply。当然,如果opApply在范围类型而不是 , 和 上调用frontpopFront那么empty这是一个编译器错误。从它的声音来看,编译器错误地选择了,opApply因为opApply使用了ref,而front没有。但是,只要没有声明,只要没有使用,front作品就很好。因此,这并不是一个问题,而是编译器在看到有和没有时错误地使用了这一事实。refforeachrefopApplyrefopApplyopApplyreffront

So, the compiler needs to be fixed, but this probably never got caught before, because it makes no sense to declare opApply on a range type like you're doing. So, I'd argue that your code needs to be changed to not declare opApply on a range type. Then you wouldn't even hit this particular bug.

That being said, the code in question in Phobos is buggy for ranges which are reference types (like classes), because it fails to call save on haystack when it iterates over it. The result of that is that the original range gets mutated to refer to the spot that's being searched for, whereas what's returned points to as far past the correct spot as the element was from the front of the haystack. So, even if you stop declaring opApply and/or the compiler bug gets fixed, std.algorithm.find will need to be fixed for your code to start working if you're using a reference type for the range.

EDIT:

Okay. That's not quite right. I have been corrected in discussing it with some compiler devs. It used to be that the range functions were favored over opApply, and that's what the spec says, but at some point, it was changed so that opApply was favored over the range functions so that a range type could iterate using opApply with foreach if that was more efficient for it (though that obviously introduces the risk of the range functions and opApply not having the same behavior, which could result in some really nasty bugs). So, the spec does not match the current behavior of the compiler, and it should work for you to declare opApply on a range type (though I'd still advise against it unless you're getting a definite performance gain out of it).

That being said, the fact that you're getting an error here is still a compiler bug. Since your opApply doesn't use ref, it won't work with a ref loop variable, whereas the range functions would, so the compiler should be calling the range functions in that case, and clearly it's not. Either way, this wasn't caught before, because almost no one uses opApply on ranges, since the only reason to do it is if there's a performance gain in doing so, and I'm sure that the fact that the spec still says that the range functions are preferred overopApply makes it so that even fewer people have tried it than might otherwise be the case.

于 2015-02-05T12:05:31.943 回答