Если вам кажется, что Новый год наступил только вчера, и вы не заметили, как прошла уже большая половина января – значит, все это время вы были заняты поиском трудноуловимых багов в поддерживаемом вами коде. А также это значит, что наша статья именно для вас. Мы, PVS-Studio, проверили open source проект 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 тесты. Поэтому прямо сейчас начинайте использовать статический анализ кода в своей работе, чтобы в Новом году и ваш код стал лучше и чище, чем в предыдущем.
Мы уже не первый раз проверяем пакеты, связанные вычислениями, статистикой, научными исследованиями. И каждый раз мы переживаем за ошибки в коде подобных проектов. Можно ли доверять данным, вычисленным с помощью этих библиотек?
Конечно, написать код без ошибок невероятно сложно, а на практике так вообще невозможно. Однако, библиотеки, используемые как строительные кирпичики в научных, медицинских, исследовательских программах должны проверяться максимально тщательно. Код должен быть чистым, насколько это вообще возможно. Ведь каждая ошибка может иметь очень неприятные последствия в будущем. По крайней мере, статический анализ для таких проектов крайне полезен.
Данную тематику мы уже затрагивали в некоторых других наших статьях, поэтому, если этот вопрос оказался для вас интересным, вы можете ознакомиться с некоторыми из них: