Если вам кажется, что Новый год наступил только вчера, и вы не заметили, как прошла уже большая половина января – значит, все это время вы были заняты поиском трудноуловимых багов в поддерживаемом вами коде. А также это значит, что наша статья именно для вас. Мы, PVS-Studio, проверили open source проект ELKI, чтобы показать вам, какие ошибки могут встретиться в коде, как хитро там они могут спрятаться, и как можно с этим бороться.

0111_ELKI_ru/image1.png

ELKI – что за библиотека?

Аббревиатура ELKI расшифровывается как Environment for Developing KDD-Applications Supported by Index-Structures. Этот проект написан на Java и предназначен для интеллектуального анализа данных. Основные пользователи данной библиотеки – студенты, исследователи, специалисты по данным и инженеры-программисты. Это неудивительно, т. к. данная библиотека разрабатывалась как раз для проведения исследований.

Алгоритмы, включенные в библиотеку, в основном, относятся к кластерному анализу и поиску выбросов, которые могут указывать на экспериментальные ошибки. С каждым годом упоминаний об исследованиях, проведенных с использованием ELKI, становится все больше и больше. На официальном сайте разработчиков можно найти целый список научных работ, которые проводились с использованием данной библиотеки. Из года в год этот список постоянно растет и дополняется, а темы научных работ становятся все разнообразнее.

Единственным препятствием для использования данной библиотеки может стать AGPL лицензия, которая требует, чтобы полный исходный код приложения был открыт для любого пользователя. Т. е. в коммерческих проектах с закрытым исходным кодом данную библиотеку использовать не получится.

Приступаем к проверке

Библиотека ELKI содержит 2 630 файлов на java, в которых 186 444 строки кода, не считая комментариев. Поэтому проект кажется довольно маленьким на фоне некоторых open source гигантов.

Однако небольшой размер библиотеки не является гарантией отсутствия в ней ошибок. Как известно, ошибки могут быть в любых проектах вне зависимости от их масштаба. В этом мы сейчас и убедимся! Приступим к рассмотрению 10 самых интересных, на мой взгляд, предупреждений, обнаруженных при просмотре отчета.

Непроверенные границы

V6001 There are identical sub-expressions 'bounds[j + 1]' to the left and to the right of the '!=' operator. CLIQUEUnit.java(252)

private boolean checkDimensions(CLIQUEUnit other, int e) {
    for(int i = 0, j = 0; i < e; i++, j += 2) {
        if (dims[i] != other.dims[i]
            || bounds[j] != other.bounds[j]
            || bounds[j + 1] != bounds[j + 1]) {
          return false;
        }
    }
    return true;
}

В блоке if метода checkDimensions значение bounds[j + 1] проверяется на неравенство со своим же собственным значением. Естественно, данное условие всегда будет ложным, и одна из границ никогда не будет проверена. То есть метод checkDimensions может вернуть при проверке значение true даже в том случае, если границы у массивов совпадать не будут.

Корректная проверка в блоке if должна выглядеть так:

bounds[j + 1] != other.bounds[j + 1]

Ленивый конструктор

V6022 Parameter 'updates' is not used inside constructor body. DataStoreEvent.java(60)

V6022 Parameter 'removals' is not used inside constructor body. DataStoreEvent.java(60)

public DataStoreEvent(DBIDs inserts, DBIDs removals, DBIDs updates) {
    super();
    this.inserts = inserts;
    this.removals = inserts;
    this.updates = inserts;
}

На данный фрагмент кода было получено два предупреждения. Здесь в конструктор DataStoreEvent передаются три параметра, два из которых для инициализации не используются. Если присмотреться к коду в конструкторе, становится понятно, что программист использовал копипаст и забыл исправить имена переменных, которые должны были участвовать в инициализации.

Если пойти еще дальше, и рассмотреть класс DataStoreEvent более детально, можно увидеть в нем три метода, которые активно используют вышеуказанный конструктор.

public static DataStoreEvent insertionEvent(DBIDs inserts) {
  return new DataStoreEvent(inserts, DBIDUtil.EMPTYDBIDS, DBIDUtil.EMPTYDBIDS);
}

public static DataStoreEvent removalEvent(DBIDs removals) {
  return new DataStoreEvent(DBIDUtil.EMPTYDBIDS, removals, DBIDUtil.EMPTYDBIDS);
}

public static DataStoreEvent updateEvent(DBIDs updates) {
  return new DataStoreEvent(DBIDUtil.EMPTYDBIDS, DBIDUtil.EMPTYDBIDS, updates);
}

Из-за некорректной инициализации в конструкторе поведение данных методов тоже будет отличаться от ожидаемого.

Корректный вариант кода в конструкторе должен быть таким:

this.inserts = inserts;
this.removals = removals;
this.updates = updates;

Непрозрачная переменная

V6012 The '?:' operator, regardless of its conditional expression, always returns one and the same value '0.5'. ClusterHullVisualization.java(173), ClusterHullVisualization.java(173)

public void fullRedraw() {
    ....
    boolean flat = (clusters.size() == topc.size());
    // Heuristic value for transparency:
    double baseopacity = flat ? 0.5 : 0.5;
    ....
}

В этом фрагменте кода значение переменной baseopacity всегда будет равно 0.5 вне зависимости от того, какое значение будет у переменной flat. Понятно, что здесь должны были быть два разных значения, но из-за невнимательности автор кода забыл исправить одно из них.

Ошибка простая и обидная. Она сразу бросается в глаза, если из метода исключить строки кода, которые не имеют отношения к данной переменной. Но обнаружить ее в методе, состоящем почти из 90 строк – непростая задача. Похоже, что именно это и стало препятствием для программиста.

Получить запредельное

V6025 Index '1' is out of bounds. GeneratorStatic.java(104)

@Override
public double[] computeMean() {
    // Not supported except for singletons.
    return points.size() == 1 ? points.get(1) : null;
}

В методе computeMean автор кода проверяет, что размер коллекции points равен единице, и, если это так, пытается вернуть из метода… элемент коллекции с индексом 1. Так как индексация начинается с нуля, исключения IndexOutOfBoundsException здесь не избежать.

Исправленный вариант кода должен выглядеть так:

return points.size() == 1 ? points.get(0) : null;

Можно ли делить на ноль?

V6020 Divide by zero. The range of the 'referenceSetSize' denominator values includes zero. PreDeConNeighborPredicate.java(138)

protected PreDeConModel computeLocalModel(DoubleDBIDList neighbors, ....) {
    final int referenceSetSize = neighbors.size();
    ....
    // Shouldn't happen:
    if(referenceSetSize < 0) {
        LOG.warning("Empty reference set – 
            should at least include the query point!");
        return new PreDeConModel(Integer.MAX_VALUE, DBIDUtil.EMPTYDBIDS);
    }
    ....
    for(int d = 0; d < dim; d++) {
        s[d] /= referenceSetSize;
        mvVar.put(s[d]);
    }
    ....
}

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

В этом фрагменте кода все зависит от размера параметра neighbors, переданного в метод computeLocalModel. Автор кода проверяет размер neighbors и отсекает значения меньше нуля проверкой в операторе if, но при этом не предпринимает никаких действий, если размер равен нулю. Т.к. проверка referenceSetSize < 0 не несет никакого смысла, и в сообщении для логирования тоже говорится про пустой set – все это очень похоже на опечатку. Скорее всего, здесь задумывалась проверка referenceSetSize == 0.

Если в данный метод все же будет передан пустой контейнер neighbors, то в цикле for произойдет деление на ноль. Остается надеяться, что такого действительно никогда не случится.

Бесконечная инициализация

V6062 Possible infinite recursion inside the 'setInitialMeans' method. Predefined.java(65), Predefined.java(66)

public void setInitialMeans(List<double[]> initialMeans) {
    this.setInitialMeans(initialMeans);
}

Этот метод из одной строки является самой настоящей рекурсией. Сложно предположить, что именно хотел здесь написать автор кода. Вероятно, единственная строка этого метода должна была выглядеть как-то так:

this.setInitialMeans(initialMeans.toArray(new double[0][0]));

Так как в этом классе есть еще один метод с таким же названием, программист, скорее всего, хотел передать данные для инициализации в него, но в итоге что-то пошло не так. Вот так, кстати, выглядит тело второго метода:

public void setInitialMeans(double[][] initialMeans) {
    double[][] vecs = initialMeans.clone(); // TODO: deep copy?
    this.initialMeans = vecs;
}

Потерянный вес

V6094 The expression was implicitly cast from 'int' type to 'double' type. Consider utilizing an explicit type cast to avoid the loss of a fractional part. An example: double A = (double)(X) / Y;. ProbabilityWeightedMoments.java(130)

public static <A> double[] alphaBetaPWM(...., final int nmom) {
    final int n = adapter.size(data);
    final double[] xmom = new double[nmom << 1];
    double aweight = 1. / n, bweight = aweight;
    for(int i = 0; i < n; i++) {
        ....
        for(int j = 1, k = 2; j < nmom; j++, k += 2) {
            xmom[k + 1] += val * (aweight *= (n - i - j + 1) / (n - j + 1));
            xmom[k + 1] += val * (bweight *= (i - j + 1) / (n - j + 1));
        }
    }
    return xmom;
}

В цикле for данного фрагмента кода происходит неявное приведение выражения (n — i — j + 1) / (n — j + 1) от типа int к типу double. Потеря точности в данном случае может быть совершенно различной: от нескольких цифр после запятой до полного обнуления веса, если число по модулю окажется меньше единицы. Скорее всего, это не совсем ожидаемое поведение, учитывая, что массив xmom имеет тип double. Убедиться в том, что программист имел здесь в виду совсем другое, помогает выражение (n – i – j + 1) / (n – j + 1). Допустим, n – j + 1 равно x. Тогда получаем выражение: (x – i) / x. Данное выражение всегда будет давать 0 при целочисленном делении, если только мы не начнем уходить в отрицательные диапазоны. Но т. к. значения n в данном фрагменте кода всегда больше нуля, можно сделать вывод, что программист не собирался здесь делить целочисленно.

Для того, чтобы избежать потери точности, необходимо явное преобразование к типу double:

xmom[k + 1] += val * (aweight *= (double) (n - i - j + 1) / (n - j + 1));
xmom[k + 1] += val * (bweight *= (double) (i - j + 1) / (n - j + 1));

Выход за границы

V6079 Value of the 'splitpoint' variable is checked after use. Potential logical error is present. KernelDensityFittingTest.java(97), KernelDensityFittingTest.java(97)

public final void testFitDoubleArray() throws IOException {
    ....
    int splitpoint = 0;
    while(fulldata[splitpoint] < splitval && splitpoint < fulldata.length) {
        splitpoint++;
    }
    ....
}

В данном фрагменте кода в цикле while сначала производится сравнение элемента массива fulldata с индексом splitpoint со значением переменной splitval, и только затем проверяется, что значение splitpoint меньше, чем размер самого массива. Две эти проверки в цикле while нужно поменять местами, иначе можно очень легко оказаться за границами массива.

Недостижимый код

V6019 Unreachable code detected. It is possible that an error is present. Tokenizer.java(172)

V6007 Expression 'c != '\n'' is always true. Tokenizer.java(169)

public String getStrippedSubstring() {
    int sstart = start, ssend = end;
    while(sstart < ssend) {
        char c = input.charAt(sstart);
        if(c != ' ' || c != '\n' || c != '\r' || c != '\t') {
            break;
        }
        ++sstart;
    }
    ....
}

На этот фрагмент кода заругались сразу две диагностики, которые в этот раз решили действовать сообща. Диагностика V6019 указала на недостижимый фрагмент кода: ++sstart, а диагностика V6007 указала на условие в операторе if, которое всегда будет истинным.

Почему в блоке if всегда будет истина? Все очень просто. В данном операторе проверяется сразу несколько условий: c != ' ', или c != '\n', или c != '\r', или c != '\t'. При любых входных данных какое-нибудь из перечисленных условий будет истинным. Даже если одна из проверок будет false, следующая проверка вернет true, и из-за оператора || (или) условие в if в итоге будет истинным. А так как условие в блоке if всегда будет истинным – будет срабатывать оператор break, досрочно завершающий цикл while, и инкремент переменной sstart никогда не будет выполнен. Именно это заметила диагностика V6019 и начала бить тревогу.

Скорее всего, программист хотел написать что-то вроде этого:

if(c != ' ' && c != '\n' && c != '\r' && c != '\t')

Переопределяй, но проверяй

V6009 Function 'equals' receives an odd argument. An object 'other.similarityFunction' is used as an argument to its own method. AbstractSimilarityAdapter.java(91)

@Override
public boolean equals(Object obj) {
    if(obj == null) {
        return false;
    }

    if(!this.getClass().equals(obj.getClass())) {
        return false;
    }

    AbstractSimilarityAdapter<?> other = (AbstractSimilarityAdapter<?>) obj;
    return other.similarityFunction.equals(other.similarityFunction);
}

Автор кода решил переопределить метод equals в классе AbstractSimilarityAdapter. Если предполагается, что в программе объекты будут храниться в контейнерах, либо проверяться на равенство, переопределение equals просто необходимо. Однако, всю задумку автора испортила последняя строка метода, в которой equals вызывается для того же самого объекта. В итоге даже самое обычное сравнение будет происходить некорректно.

Корректный код должен был выглядеть так:

return this.similarityFunction.equals(other.similarityFunction);

Хочется заметить, что данный паттерн ошибок часто встречается в программах на разных языках, а не только в Java. Об этом у нас есть статья 'Зло живет в функциях сравнения'. Обязательно почитайте ее, если вам интересно узнать, почему же программисты часто допускают ошибки в достаточно простых функциях, предназначенных для сравнения двух объектов.

Подведем итоги

Как видите, в любом проекте могут появиться ошибки. Одни из них — простые и обидные, другие – хитрые и коварные. И не имеет никакого значения – маленький ваш проект, или большой. Не имеет значения – профессиональный вы разработчик, или только начинаете писать код. Ошибки могут появиться в любом месте вашей программы, и надежно спрятаться от ваших глаз.

Для каждого разработчика и для каждого проекта статический анализ кода – это незаменимый инструмент. Такой же незаменимый, как review кода, или unit тесты. Поэтому прямо сейчас начинайте использовать статический анализ кода в своей работе, чтобы в Новом году и ваш код стал лучше и чище, чем в предыдущем.

В заключение

Мы уже не первый раз проверяем пакеты, связанные вычислениями, статистикой, научными исследованиями. И каждый раз мы переживаем за ошибки в коде подобных проектов. Можно ли доверять данным, вычисленным с помощью этих библиотек?

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

Данную тематику мы уже затрагивали в некоторых других наших статьях, поэтому, если этот вопрос оказался для вас интересным, вы можете ознакомиться с некоторыми из них:

Как PVS-Studio ELKI в январе проверяли