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

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

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|ошибка: 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) оценок pred.

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


person E_net4 the curator    schedule 03.02.2015    source источник


Ответы (1)


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

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

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

ИЗМЕНИТЬ:

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

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

person Jonathan M Davis    schedule 05.02.2015
comment
Действительно, это зацепило. Также кажется, что сообщество D могло бы использовать еще несколько невежественных программистов для поиска подобных недостатков. ;) - person E_net4 the curator; 05.02.2015