Должен ли std.algorithm.find требовать ссылки на элементы диапазона?

Question

Я работал над классом конечного диапазона произвольного доступа. При выполнении нескольких тестов на нем:

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, касающуюся последней строки в приведенном выше фрагменте кода: "attribute.d|4838|error: foreach: не могу сделать 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);

Который, по моей интерпретации, не следовало искать.

Также цитирую std.algorithm.all, который, похоже, не требует итерации для ссылок:

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

Возвращает true тогда и только тогда, когда все значения v, найденные в диапазоне входного диапазона, удовлетворяют предикату pred. Выполняет (максимум) Ο(range.length) оценки пред.

Так это ошибка в библиотеке Фобоса, и std.algorithm.find должен итерировать по значению в первую очередь? Или я что-то упустил?

Answer 1

Даже не имеет смысла объявлять opApply на объекте, который должен быть диапазоном, потому что, если это диапазон, то функции на основе диапазона будут использоваться для foreachне opApply, Конечно, если opApply вызывается по типу диапазона вместо front, popFront, а также emptyтогда это ошибка компилятора. Из звуков этого компилятор неправильно выбирает opApply поскольку opApply использования ref, в то время как front не. Тем не менее front работает просто отлично без ref с foreach который использует ref пока opApply не объявлено Итак ref это не проблема, а тот факт, что компилятор неправильно использует opApply когда он видит это opApply имеет ref а также front не делает.

Итак, компилятор должен быть исправлен, но это, вероятно, никогда не было поймано раньше, потому что нет смысла объявлять opApply на типе диапазона, как вы делаете. Итак, я бы сказал, что ваш код должен быть изменен, чтобы не объявлять opApply по типу диапазона. Тогда вы бы даже не попали в эту конкретную ошибку.

При этом рассматриваемый код на Фобосе содержит ошибки для диапазонов, которые являются ссылочными типами (например, классы), потому что он не может вызвать save на haystack когда он перебирает его. Результатом этого является то, что исходный диапазон видоизменяется для ссылки на искомую точку, в то время как возвращаемая точка указывает на то, насколько далеко за правильное место находится элемент, находящийся в передней части стога сена. Так что, даже если вы перестанете декларировать opApply и / или исправлена ​​ошибка компилятора, чтобы ваш код начал работать, нужно исправить std.algorithm.find, если вы используете ссылочный тип для диапазона.

РЕДАКТИРОВАТЬ:

Хорошо. Это не совсем верно. Я был исправлен в обсуждении этого с некоторыми разработчиками компилятора. Раньше считалось, что функции диапазона были предпочтительнее, чем opApplyи это то, что говорит спецификация, но в какой-то момент, это было изменено так, чтобы opApply было отдано предпочтение по сравнению с функциями диапазона, чтобы тип диапазона мог перебирать opApply с foreach если это было бы более эффективным для него (хотя это, очевидно, представляет риск для функций диапазона и opApply не иметь такого же поведения, что может привести к некоторым действительно неприятным ошибкам). Таким образом, спецификация не соответствует текущему поведению компилятора, и она должна работать для вас, чтобы объявить opApply на типе диапазона (хотя я все еще советую против этого, если вы не получаете определенный выигрыш в производительности).

Тем не менее, тот факт, что вы получаете ошибку здесь, все еще является ошибкой компилятора. Так как ваш opApply не использует ref, это не будет работать с ref переменная цикла, в то время как функции диапазона будут, так что компилятор должен вызывать функции диапазона в этом случае, и, очевидно, это не так. В любом случае, это не было поймано раньше, потому что почти никто не использует opApply на диапазонах, поскольку единственная причина сделать это, если есть прирост производительности при этом, и я уверен, что тот факт, что спецификация все еще говорит, что функции диапазона предпочтительнее, чемopApply делает так, что даже меньше людей попробовали это, чем могло бы быть в противном случае.