Контроль диапазонов целых чисел в FindBugs
FindBugs — это статический анализатор кода для Java с открытым исходным кодом (под LGPL). Он содержит множество детекторов, которые определяют те или иные проблемы в коде. С недавних пор я являюсь участником проекта и пишу для него новые детекторы. Об одном из них я и расскажу в этой статье. Также мы посмотрим примеры багов, найденных в реальных проектах.Устройство FindBugsFindBugs анализирует не исходники, а байт-код. У этого метода есть некоторые недостатки. Нельзя написать детектор, который основан только на неправильном форматировании кода (например, возможно пропущенное else в else if, как V646 в PVS-Studio). Нельзя детектировать некоторые ситуации, в которых генерируется одинаковый байт-код. Например, хорошо бы детектировать такой странный код (на который выдаёт предупреждение IDEA и та же PVS-Studio):
while (a < 5) {
a++;
return;
}
Но если мы заменим while на if, компиляторы сгенерируют точно такой же байт-код, поэтому FindBugs не может увидеть разницы. Важно помнить про это, когда вы используете или планируете расширять FindBugs.Для работы с байт-кодом используется в основном Byte Code Engineering Library (6.0-SNAPSHOT) от Apache и иногда ASM 5.0.2. Видимо, такой расклад случился по историческим причинам: когда проект FindBugs начинался, BCEL была единственным подходящим вариантом, но сейчас она, к сожалению, почти не развивается. По сути сами авторы FindBugs дорабатывают её, чтобы можно было анализировать новые версии class-файлов.
Основная часть работы FindBugs выполняется в детекторах, которые и занимаются выдачей предупреждений. Бывают также специальные детекторы, которые собирают какую-нибудь информацию о коде (например, строят граф вызовов) и сохраняют её для дальнейшего использования другими детекторами. FindBugs работает в два прохода: на первом проходе работают в основном эти специальные детекторы и они анализируют не только классы самого проекта, но и классы используемых библиотек. Также есть фабрики анализов, которые строят определённый анализ класса или метода по требованию того или иного детектора (например, анализ потока null и non-null значений внутри метода).
Задача Мне захотелось отлавливать логические ошибки вроде таких: int test (int x) { if (x > 10 && x > 5) { return 1; } return 0; } Здесь очевидно второе условие бесполезно, потому что если x больше 10, то он хоть как больше 5. Приведённый пример очень простой, хотя и такие ошибки встречаются в реальном коде. В целом задача состоит в том, чтобы найти условия на целые числа, которые для любого возможного значения числа всегда истинны или всегда ложны.
Граф потока управления
В теории компиляции есть такая штука — граф потока управления (control flow graph, CFG). Это похоже на старую добрую блок-схему, построенную по программному коду: вершины графа — это базовые блоки, код в которых выполняется линейно без всяких переходов, а рёбра — возможные направления перехода. Граф потока управления может быть довольно большим даже для простого метода, потому что большинство инструкций может сгенерировать исключение, для которого добавляется ребро. Граф потока управления для каждого метода уже строится в FindBugs, поэтому им можно пользоваться. Вот как бы выглядел такой граф для метода, приведённого выше: 
Для нашей задачи сперва надо выбрать все параметры и локальные переменные, которые могут участвовать в анализе. Пока я ограничился только теми, которые никогда не меняются (возможно, в будущем ограничение будет ослаблено). То есть нас интересуют параметры, которые ни разу не присваивают, и переменные, которые присваивают ровно один раз. Такой список легко составить, просто пробежавшись по инструкциям метода в поисках инструкций записи в локальную переменную. Для каждой переменной мы изначально устанавливаем допустимый диапазон значений. Например, для типа int это будет [Integer.MIN_VALUE…Integer.MAX_VALUE].
Далее мы перебираем те узлы CFG, которые содержат условие. Если это сравнение интересующей нас переменной с константой, то мы разбиваем соответствующий интервал согласно условию. Например, для условия x > 5 мы получим [Integer.MIN_VALUE…5] + [6…Integer.MAX_VALUE], а для x!= 0 получим три интервала: [Integer.MIN_VALUE…-1] + {0} + [1…Integer.MAX_VALUE]. Также для каждого такого условия сохраняется интервал, который условию удовлетворяет.
Затем для каждой интересующей нас переменной мы пробегаемся по всем интервалам области определения и для каждого интервала гуляем по графу потока, начиная от входного узла. При этом если мы попадаем в условный узел, связанный с данной переменной, то идём только по одному ребру в зависимости от того, выполняется ли условие на данном интервале, и помечаем, по какому мы прошли. Для всех прочих узлов мы проходим всевозможные исходящие рёбра. Наша маленький метод разбивает область определения x на три интервала, для которых обход графа будет выглядеть так: 
Заметьте, что в первых двух случаях получилось одно и то же. В конце остаётся лишь найти рёбра, которых мы ни разу не достигли и сформировать по ним сообщение об ошибке. Если конечная вершина этого ребра также оказалась не достигнута, это означает, что у нас не просто бесполезное условие, но и имеется код, который никогда не будет выполнен. В этом случае я повышаю приоритет сообщения об ошибке. Для вышеприведённого примера имеется недостижимое ребро, но достижимы все вершины:
А вот простой метод, в котором появляется недостижимая вершина (тело оператора if):
int test (int x) { if (x > 10 && x < 5 ) { return 1; } return 0; } CFG будет выглядеть так:
finally Всё это классно работало, пока я не столкнулся с finally. Компиляторы дублируют finally-блоки в байт-коде, из-за чего появляются недостижимые условия, которых не было в исходнике. Скажем, такой простой пример: int test (int x) { try { if (x > 0) return -1; return 0; } finally { if (x <= 0 ) log.info("x <= 0!"); } } Код вполне нормальный, но в процессе компиляции он превращается во что-то такое (без учёта возможных исключений):
int test (int x) { if (x > 0) { if (x <= 0 ) log.info("x <= 0!"); return -1; } if( x <= 0 ) log.info("x <= 0!"); return 0; } В результате наш новый детектор жалуется, что в первом случае x <= 0 всегда ложно и есть мёртвый код, а во втором, что x <= 0 всегда истинно. Готового решения для разбора таких ситуаций в FindBugs не было. Только при null-анализе делаются некоторые предположения на основе таблицы номеров строк. Мне это показалось ненадёжным (тем более этой таблицы может и не быть), и я написал отдельный анализатор, который с небольшой долей эвристики находит в байт-коде дублирующие finally-блоки и может для заданного ребра CFG выдать все его дубликаты. Собственно, в процессе этой работы и родилась мысль написать шуточную статью. Теперь я выдаю ошибку, только если во всех дубликатах ребро не было достигнуто.
Найденные ошибки Теперь самая весёлая часть. Я обычно для тестов анализирую пачку проектов с открытыми исходниками, поэтому примеры будут из разных проектов.Ошибки из-за диапазона значений типа Это побочный эффект анализа, про который я сразу не подумал: иногда условие бесполезно не потому, что выше было противоречащее ему условие, а потому, что тип переменной ограничен. Я сделал для него отдельное сообщение. Вот пример, про который я даже не буду говорить, из какого он проекта. Этот метод с небольшими вариациями бездумно скопирован в десяток проектов, где используется XML: public final static boolean isNameStartChar (char ch) { return (ch > bA && ch < aZ) || (ch > ba && ch < az) || (ch == ':') || (ch == '_') || (ch > 0xBF && ch < 0xD7) || (ch > 0xD7 && ch < 0xF7) || (ch > 0xF7 && ch < 0x300) || (ch > 0×36F && ch < 0x37E) || (ch > 0×37E && ch < 0x2000) || (ch > 0×200B && ch < 0x200E) || (ch > 0×206F && ch < 0x2190) || (ch > 0×2BFF && ch < 0x2FF0) || (ch > 0×3000 && ch < 0xD800) || (ch > 0xF900 && ch < 0xFDD0) || (ch > 0xFDEF && ch < 0xFFFE) || (ch > 0×0FFFF && ch < 0xF0000); // ch > 0xFFFF всегда истинно } Последняя пара условий бессмысленна: значение переменной типа char не может быть больше 0xFFFF. Если авторы планировали поддерживать такие символы, надо анализировать суррогатные пары UTF-16, анализом одного char тут не обойдёшься.Вот более конкретное — Utility#encodeRun из проекта IBM ICU:
private static final char ESCAPE = '\uA5A5';
private static final Использован && вместо ||
Одна из частых грубых ошибок. Обычно встречается в проверке входных параметров, которая не всегда должным образом покрыта юнит-тестами. Вот, например, в SegmentArrayWithData#setElementAt в IntelliJ IDEA:
public void setElementAt (int i, int startOffset, int endOffset, int data) {
if (data < 0 && data > Short.MAX_VALUE) throw new IndexOutOfBoundsException («data out of short range» + data);
…
}
Здесь data > Short.MAX_VALUE бессмысленно, потому что не может быть число одновременно меньше 0 и больше 32767. В результате формируется мёртвый код: исключение никогда не будет выкинуто. Подобная бага была найдена в различных проектах, но меня удивило увидеть это в IDEA: у них самих встроенный серьёзный статический анализатор, который наверняка должен ловить такое. Возможно, проглядели.Использован || вместо &&
Такое встречается существенно реже. Вот снова из ICU — ULocale#parseAcceptLanguage:
case 8: // before q value fraction part
if ('0' <= c || c <= '9') { // c <= '9' всегда истинно
...
} else {
// invalid
state = -1;
}
break;
Условие c Одно и то же условие в двух ветках
Пример из Eclipse Mylyn — DefaultXmlStreamWriter#printEscaped:
private static void printEscaped(PrintWriter writer, int ch, boolean attribute) throws IOException {
String ref = getEntityRef(ch, attribute);
if (ref != null) {
writer.write('&');
writer.write(ref);
writer.write(';');
} else if (ch == '\r' || ch == 0x0085 || ch == 0x2028) {
printHex(writer, ch);
} else if ((ch >= ' ' && ch!= 160 && isUtf8Printable ((char) ch) && XML11Char.isXML11ValidLiteral (ch))
|| ch == '\t' || ch == '\n' || ch == '\r') { // ch == '\r' всегда ложно
writer.write ((char) ch);
} else {
printHex (writer, ch);
}
}
Здесь условие ch == '\r' имеется в двух ветках else if. Сработает, конечно, только первое. Мёртвого кода нет, но неясно, что имел в виду автор.Взаимоисключающие параграфы
Вот довольно свежий код из того же Mylyn — EscapeBlock#canStart:
public boolean canStart (String line, int lineOffset) {
if (lineOffset == 0) {
Matcher matcher = START_PATTERN.matcher (line);
if (lineOffset > 0) { // lineOffset > 0 всегда ложно
matcher.region (lineOffset, line.length ());
}
if (matcher.matches ()) {
return true;
}
}
return false;
}
Если уж lineOffset равен 0, то он никак не может быть больше 0.Забыли, что было раньше?
Пример из проекта Jmol — GromacsReader#readAtoms
for (int i = 0; i < modelAtomCount; ++i) {
rd();
int len = line.length();
if (len != 44 && len != 68) {
Logger.warn("line cannot be read for GROMACS atom data: " + line);
continue;
}
...
if (len < 69) // len < 69 всегда истинно
continue;
float vx = parseFloatRange(line, 44, 52) * 10;
float vy = parseFloatRange(line, 52, 60) * 10;
...
}
В начале цикла проверяется длина прочитанной из файла строки. Если она не равна 44 или 68, выдаём предупреждение и переходим к следующей итерации цикла. Ближе к концу итерации ещё одна проверка на len: теперь уже if (len Запутались в операторах сравнения
Снова ICU — CollationParsedRuleBuilder#isJamo:
private static final boolean isJamo(char ch) {
return (ch >= 0×1100 && ch <= 0x1112) || (ch >= 0×1175 && ch <= 0x1161) // ch <= 0x1161 всегда ложно
|| (ch >= 0×11A8 && ch <= 0x11C2);
}
Средняя пара условий находит числа в диапазоне от 0x1175 до 0x1161. Разумеется, таких чисел быть не может, так как 0x1161 меньше, чем 0x1175. Здесь мы выдаём предупреждение, что условие ch Переполнение при вычислениях
Вот Andrey2008 постоянно спрашивают, может ли он показать весёлые баги из кода PVS-Studio, найденные PVS-Studio, а он отвечает, что все баги обычно исправляются сразу, так как используется инкрементальная проверка, и они даже в репозиторий не попадают. В целом это справедливо и для FindBugs: Eclipse-проект в FindBugs настроен на инкрементальную проверку, так что трудно найти что-то серьёзное в FindBugs, проверяя его им же самим. Но всё меняется, когда разрабатываешь новый детектор. Тогда он действительно может найти очень вкусную багу в старом коде, что и случилось. Посмотрите метод DumbMethods#checkForCompatibleLongComparison
private void checkForCompatibleLongComparison(OpcodeStack.Item left, OpcodeStack.Item right) {
if (left.getSpecialKind() == Item.RESULT_OF_I2L && right.getConstant() != null) {
long value = ((Number) right.getConstant()).longValue();
if ( (value > Integer.MAX_VALUE || value < Integer.MIN_VALUE)) {
int priority = Priorities.HIGH_PRIORITY;
if (value == Integer.MAX_VALUE+1 || value == Integer.MIN_VALUE -1) { // оба условия всегда ложны
priority = Priorities.NORMAL_PRIORITY;
}
...
}
Данный код (написанный, кстати, более четырёх лет назад) выполняется в случае, если в анализируемом исходнике число типа int сравнивается с числом типа long, которое не влезает в диапазон int. Такое сравнение бессмысленно, поэтому здесь генерируется предупреждение INT_BAD_COMPARISON_WITH_INT_VALUE. Предполагалось установить приоритет пониже, если сравнение выполняется с числом, которое на границе диапазона целых чисел (Integer.MAX_VALUE+1 или Integer.MIN_VALUE-1). Дело однако в том, что эти выражения сами вычисляются в целых числах и возникает переполнение: вместо Integer.MAX_VALUE+1 мы получаем Integer.MIN_VALUE, а вместо Integer.MIN_VALUE-1 получаем Integer.MAX_VALUE. Причём это вычисление выполняет компилятор, и в байткод попадает уже результирующее число. Здесь-то мой новый детектор и блеснул: из вышестоящего условия следует, что ни Integer.MIN_VALUE, ни Integer.MAX_VALUE не может быть в value в данной точке. В результате условие никогда не выполнится, и приоритет никогда не будет понижен. Конечно, следовало написать
if (value == Integer.MAX_VALUE+1L || value == Integer.MIN_VALUE-1L)
Понятно, почему этот баг оставался незамеченным годами: пользователи могли и не догадываться о намерении авторов понизить приоритет в данном случае, а тесты в FindBugs обычно проверяют, есть ли определённое предупреждение на определённом коде или нет, но не проверяют его приоритет.Перестраховка
Довольно много сообщений выдаётся о перестраховочных условиях вроде таких:
if( x > 0) { … } else if (x <= 0 ) { ... }
Второе условие очевидно не нужно, хотя кто-то может поспорить, что оно дополнительно документирует код. Всё же я считаю, что если пояснение нужно, его лучше написать в комментарии. Во всяком случае, ранее FindBugs уже ругался на такой код:
if( obj == null ) { ... } else if( obj != null ) { ... }
Поэтому я считаю, что не нарушил общей концепции.Ещё встречается такой код:
if (x > 0) {
… // много строчек
if (x > 0) {
… // ещё код
}
…
}
Обычно тут ошибки нет, но выглядит так, будто автор уже сам не помнит, в какой он ветке кода. Возможно, это признак того, что метод сильно сложный.Заключение
Желающие испытать новый детектор могут выкачать код из нашего репозитория и скомпилировать ant’ом. Если кому-то лень компилировать, я сделал неофициальные сборки из текущего кода — findbugs.jar и Eclipse update site (к сожалению, официальный Eclipse daily site не работает). Новые предупреждения называются UC_USELESS_CONDITION и UC_USELESS_CONDITION_TYPE (категория Dodgy code).Если кому интересна реализация, большая часть кода в классе ValueRangeAnalysisFactory, сам детектор — RedundantConditions, а поиск дублирующихся finally-блоков — FinallyDuplicatesInfoFactory. Код ещё неокончательный, но вполне рабочий. Могут быть ложные сработки в assert’ах, с этим будем бороться. Ошибки есть в любой программе, а статический анализ — это хорошо.
